1/* Functions to support general ended bitmaps. 2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "rtl.h" 27#include "flags.h" 28#include "obstack.h" 29#include "ggc.h" 30#include "bitmap.h" 31 32/* Global data */ 33bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ 34bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ 35static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of 36 GC'd elements. */ 37 38static void bitmap_elem_to_freelist (bitmap, bitmap_element *); 39static void bitmap_element_free (bitmap, bitmap_element *); 40static bitmap_element *bitmap_element_allocate (bitmap); 41static int bitmap_element_zerop (bitmap_element *); 42static void bitmap_element_link (bitmap, bitmap_element *); 43static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); 44static void bitmap_elt_clear_from (bitmap, bitmap_element *); 45static bitmap_element *bitmap_find_bit (bitmap, unsigned int); 46 47 48/* Add ELEM to the appropriate freelist. */ 49static inline void 50bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) 51{ 52 bitmap_obstack *bit_obstack = head->obstack; 53 54 elt->next = NULL; 55 if (bit_obstack) 56 { 57 elt->prev = bit_obstack->elements; 58 bit_obstack->elements = elt; 59 } 60 else 61 { 62 elt->prev = bitmap_ggc_free; 63 bitmap_ggc_free = elt; 64 } 65} 66 67/* Free a bitmap element. Since these are allocated off the 68 bitmap_obstack, "free" actually means "put onto the freelist". */ 69 70static inline void 71bitmap_element_free (bitmap head, bitmap_element *elt) 72{ 73 bitmap_element *next = elt->next; 74 bitmap_element *prev = elt->prev; 75 76 if (prev) 77 prev->next = next; 78 79 if (next) 80 next->prev = prev; 81 82 if (head->first == elt) 83 head->first = next; 84 85 /* Since the first thing we try is to insert before current, 86 make current the next entry in preference to the previous. */ 87 if (head->current == elt) 88 { 89 head->current = next != 0 ? next : prev; 90 if (head->current) 91 head->indx = head->current->indx; 92 else 93 head->indx = 0; 94 } 95 bitmap_elem_to_freelist (head, elt); 96} 97 98/* Allocate a bitmap element. The bits are cleared, but nothing else is. */ 99 100static inline bitmap_element * 101bitmap_element_allocate (bitmap head) 102{ 103 bitmap_element *element; 104 bitmap_obstack *bit_obstack = head->obstack; 105 106 if (bit_obstack) 107 { 108 element = bit_obstack->elements; 109 110 if (element) 111 /* Use up the inner list first before looking at the next 112 element of the outer list. */ 113 if (element->next) 114 { 115 bit_obstack->elements = element->next; 116 bit_obstack->elements->prev = element->prev; 117 } 118 else 119 /* Inner list was just a singleton. */ 120 bit_obstack->elements = element->prev; 121 else 122 element = XOBNEW (&bit_obstack->obstack, bitmap_element); 123 } 124 else 125 { 126 element = bitmap_ggc_free; 127 if (element) 128 /* Use up the inner list first before looking at the next 129 element of the outer list. */ 130 if (element->next) 131 { 132 bitmap_ggc_free = element->next; 133 bitmap_ggc_free->prev = element->prev; 134 } 135 else 136 /* Inner list was just a singleton. */ 137 bitmap_ggc_free = element->prev; 138 else 139 element = GGC_NEW (bitmap_element); 140 } 141 142 memset (element->bits, 0, sizeof (element->bits)); 143 144 return element; 145} 146 147/* Remove ELT and all following elements from bitmap HEAD. */ 148 149void 150bitmap_elt_clear_from (bitmap head, bitmap_element *elt) 151{ 152 bitmap_element *prev; 153 bitmap_obstack *bit_obstack = head->obstack; 154 155 if (!elt) return; 156 157 prev = elt->prev; 158 if (prev) 159 { 160 prev->next = NULL; 161 if (head->current->indx > prev->indx) 162 { 163 head->current = prev; 164 head->indx = prev->indx; 165 } 166 } 167 else 168 { 169 head->first = NULL; 170 head->current = NULL; 171 head->indx = 0; 172 } 173 174 /* Put the entire list onto the free list in one operation. */ 175 if (bit_obstack) 176 { 177 elt->prev = bit_obstack->elements; 178 bit_obstack->elements = elt; 179 } 180 else 181 { 182 elt->prev = bitmap_ggc_free; 183 bitmap_ggc_free = elt; 184 } 185} 186 187/* Clear a bitmap by freeing the linked list. */ 188 189inline void 190bitmap_clear (bitmap head) 191{ 192 if (head->first) 193 bitmap_elt_clear_from (head, head->first); 194} 195 196/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize 197 the default bitmap obstack. */ 198 199void 200bitmap_obstack_initialize (bitmap_obstack *bit_obstack) 201{ 202 if (!bit_obstack) 203 bit_obstack = &bitmap_default_obstack; 204 205#if !defined(__GNUC__) || (__GNUC__ < 2) 206#define __alignof__(type) 0 207#endif 208 209 bit_obstack->elements = NULL; 210 bit_obstack->heads = NULL; 211 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, 212 __alignof__ (bitmap_element), 213 obstack_chunk_alloc, 214 obstack_chunk_free); 215} 216 217/* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, 218 release the default bitmap obstack. */ 219 220void 221bitmap_obstack_release (bitmap_obstack *bit_obstack) 222{ 223 if (!bit_obstack) 224 bit_obstack = &bitmap_default_obstack; 225 226 bit_obstack->elements = NULL; 227 bit_obstack->heads = NULL; 228 obstack_free (&bit_obstack->obstack, NULL); 229} 230 231/* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create 232 it on the default bitmap obstack. */ 233 234bitmap 235bitmap_obstack_alloc (bitmap_obstack *bit_obstack) 236{ 237 bitmap map; 238 239 if (!bit_obstack) 240 bit_obstack = &bitmap_default_obstack; 241 map = bit_obstack->heads; 242 if (map) 243 bit_obstack->heads = (void *)map->first; 244 else 245 map = XOBNEW (&bit_obstack->obstack, bitmap_head); 246 bitmap_initialize (map, bit_obstack); 247 248 return map; 249} 250 251/* Create a new GCd bitmap. */ 252 253bitmap 254bitmap_gc_alloc (void) 255{ 256 bitmap map; 257 258 map = GGC_NEW (struct bitmap_head_def); 259 bitmap_initialize (map, NULL); 260 261 return map; 262} 263 264/* Release an obstack allocated bitmap. */ 265 266void 267bitmap_obstack_free (bitmap map) 268{ 269 if (map) 270 { 271 bitmap_clear (map); 272 map->first = (void *)map->obstack->heads; 273 map->obstack->heads = map; 274 } 275} 276 277 278/* Return nonzero if all bits in an element are zero. */ 279 280static inline int 281bitmap_element_zerop (bitmap_element *element) 282{ 283#if BITMAP_ELEMENT_WORDS == 2 284 return (element->bits[0] | element->bits[1]) == 0; 285#else 286 unsigned i; 287 288 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 289 if (element->bits[i] != 0) 290 return 0; 291 292 return 1; 293#endif 294} 295 296/* Link the bitmap element into the current bitmap linked list. */ 297 298static inline void 299bitmap_element_link (bitmap head, bitmap_element *element) 300{ 301 unsigned int indx = element->indx; 302 bitmap_element *ptr; 303 304 /* If this is the first and only element, set it in. */ 305 if (head->first == 0) 306 { 307 element->next = element->prev = 0; 308 head->first = element; 309 } 310 311 /* If this index is less than that of the current element, it goes someplace 312 before the current element. */ 313 else if (indx < head->indx) 314 { 315 for (ptr = head->current; 316 ptr->prev != 0 && ptr->prev->indx > indx; 317 ptr = ptr->prev) 318 ; 319 320 if (ptr->prev) 321 ptr->prev->next = element; 322 else 323 head->first = element; 324 325 element->prev = ptr->prev; 326 element->next = ptr; 327 ptr->prev = element; 328 } 329 330 /* Otherwise, it must go someplace after the current element. */ 331 else 332 { 333 for (ptr = head->current; 334 ptr->next != 0 && ptr->next->indx < indx; 335 ptr = ptr->next) 336 ; 337 338 if (ptr->next) 339 ptr->next->prev = element; 340 341 element->next = ptr->next; 342 element->prev = ptr; 343 ptr->next = element; 344 } 345 346 /* Set up so this is the first element searched. */ 347 head->current = element; 348 head->indx = indx; 349} 350 351/* Insert a new uninitialized element into bitmap HEAD after element 352 ELT. If ELT is NULL, insert the element at the start. Return the 353 new element. */ 354 355static bitmap_element * 356bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) 357{ 358 bitmap_element *node = bitmap_element_allocate (head); 359 node->indx = indx; 360 361 if (!elt) 362 { 363 if (!head->current) 364 { 365 head->current = node; 366 head->indx = indx; 367 } 368 node->next = head->first; 369 if (node->next) 370 node->next->prev = node; 371 head->first = node; 372 node->prev = NULL; 373 } 374 else 375 { 376 gcc_assert (head->current); 377 node->next = elt->next; 378 if (node->next) 379 node->next->prev = node; 380 elt->next = node; 381 node->prev = elt; 382 } 383 return node; 384} 385 386/* Copy a bitmap to another bitmap. */ 387 388void 389bitmap_copy (bitmap to, bitmap from) 390{ 391 bitmap_element *from_ptr, *to_ptr = 0; 392 393 bitmap_clear (to); 394 395 /* Copy elements in forward direction one at a time. */ 396 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) 397 { 398 bitmap_element *to_elt = bitmap_element_allocate (to); 399 400 to_elt->indx = from_ptr->indx; 401 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); 402 403 /* Here we have a special case of bitmap_element_link, for the case 404 where we know the links are being entered in sequence. */ 405 if (to_ptr == 0) 406 { 407 to->first = to->current = to_elt; 408 to->indx = from_ptr->indx; 409 to_elt->next = to_elt->prev = 0; 410 } 411 else 412 { 413 to_elt->prev = to_ptr; 414 to_elt->next = 0; 415 to_ptr->next = to_elt; 416 } 417 418 to_ptr = to_elt; 419 } 420} 421 422/* Find a bitmap element that would hold a bitmap's bit. 423 Update the `current' field even if we can't find an element that 424 would hold the bitmap's bit to make eventual allocation 425 faster. */ 426 427static inline bitmap_element * 428bitmap_find_bit (bitmap head, unsigned int bit) 429{ 430 bitmap_element *element; 431 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; 432 433 if (head->current == 0 434 || head->indx == indx) 435 return head->current; 436 437 if (head->indx < indx) 438 /* INDX is beyond head->indx. Search from head->current 439 forward. */ 440 for (element = head->current; 441 element->next != 0 && element->indx < indx; 442 element = element->next) 443 ; 444 445 else if (head->indx / 2 < indx) 446 /* INDX is less than head->indx and closer to head->indx than to 447 0. Search from head->current backward. */ 448 for (element = head->current; 449 element->prev != 0 && element->indx > indx; 450 element = element->prev) 451 ; 452 453 else 454 /* INDX is less than head->indx and closer to 0 than to 455 head->indx. Search from head->first forward. */ 456 for (element = head->first; 457 element->next != 0 && element->indx < indx; 458 element = element->next) 459 ; 460 461 /* `element' is the nearest to the one we want. If it's not the one we 462 want, the one we want doesn't exist. */ 463 head->current = element; 464 head->indx = element->indx; 465 if (element != 0 && element->indx != indx) 466 element = 0; 467 468 return element; 469} 470 471/* Clear a single bit in a bitmap. */ 472 473void 474bitmap_clear_bit (bitmap head, int bit) 475{ 476 bitmap_element *ptr = bitmap_find_bit (head, bit); 477 478 if (ptr != 0) 479 { 480 unsigned bit_num = bit % BITMAP_WORD_BITS; 481 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 482 ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num); 483 484 /* If we cleared the entire word, free up the element. */ 485 if (bitmap_element_zerop (ptr)) 486 bitmap_element_free (head, ptr); 487 } 488} 489 490/* Set a single bit in a bitmap. */ 491 492void 493bitmap_set_bit (bitmap head, int bit) 494{ 495 bitmap_element *ptr = bitmap_find_bit (head, bit); 496 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 497 unsigned bit_num = bit % BITMAP_WORD_BITS; 498 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; 499 500 if (ptr == 0) 501 { 502 ptr = bitmap_element_allocate (head); 503 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; 504 ptr->bits[word_num] = bit_val; 505 bitmap_element_link (head, ptr); 506 } 507 else 508 ptr->bits[word_num] |= bit_val; 509} 510 511/* Return whether a bit is set within a bitmap. */ 512 513int 514bitmap_bit_p (bitmap head, int bit) 515{ 516 bitmap_element *ptr; 517 unsigned bit_num; 518 unsigned word_num; 519 520 ptr = bitmap_find_bit (head, bit); 521 if (ptr == 0) 522 return 0; 523 524 bit_num = bit % BITMAP_WORD_BITS; 525 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 526 527 return (ptr->bits[word_num] >> bit_num) & 1; 528} 529 530#if GCC_VERSION < 3400 531/* Table of number of set bits in a character, indexed by value of char. */ 532static unsigned char popcount_table[] = 533{ 534 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, 535 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, 536 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, 537 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, 538 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, 539 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, 540 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, 541 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, 542}; 543 544static unsigned long 545bitmap_popcount (BITMAP_WORD a) 546{ 547 unsigned long ret = 0; 548 unsigned i; 549 550 /* Just do this the table way for now */ 551 for (i = 0; i < BITMAP_WORD_BITS; i+= 8) 552 ret += popcount_table[(a >> i) & 0xff]; 553 return ret; 554} 555#endif 556/* Count the number of bits set in the bitmap, and return it. */ 557 558unsigned long 559bitmap_count_bits (bitmap a) 560{ 561 unsigned long count = 0; 562 bitmap_element *elt; 563 unsigned ix; 564 565 for (elt = a->first; elt; elt = elt->next) 566 { 567 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 568 { 569#if GCC_VERSION >= 3400 570 /* Note that popcountl matches BITMAP_WORD in type, so the actual size 571 of BITMAP_WORD is not material. */ 572 count += __builtin_popcountl (elt->bits[ix]); 573#else 574 count += bitmap_popcount (elt->bits[ix]); 575#endif 576 } 577 } 578 return count; 579} 580 581 582 583/* Return the bit number of the first set bit in the bitmap. The 584 bitmap must be non-empty. */ 585 586unsigned 587bitmap_first_set_bit (bitmap a) 588{ 589 bitmap_element *elt = a->first; 590 unsigned bit_no; 591 BITMAP_WORD word; 592 unsigned ix; 593 594 gcc_assert (elt); 595 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; 596 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 597 { 598 word = elt->bits[ix]; 599 if (word) 600 goto found_bit; 601 } 602 gcc_unreachable (); 603 found_bit: 604 bit_no += ix * BITMAP_WORD_BITS; 605 606#if GCC_VERSION >= 3004 607 gcc_assert (sizeof(long) == sizeof (word)); 608 bit_no += __builtin_ctzl (word); 609#else 610 /* Binary search for the first set bit. */ 611#if BITMAP_WORD_BITS > 64 612#error "Fill out the table." 613#endif 614#if BITMAP_WORD_BITS > 32 615 if (!(word & 0xffffffff)) 616 word >>= 32, bit_no += 32; 617#endif 618 if (!(word & 0xffff)) 619 word >>= 16, bit_no += 16; 620 if (!(word & 0xff)) 621 word >>= 8, bit_no += 8; 622 if (!(word & 0xf)) 623 word >>= 4, bit_no += 4; 624 if (!(word & 0x3)) 625 word >>= 2, bit_no += 2; 626 if (!(word & 0x1)) 627 word >>= 1, bit_no += 1; 628 629 gcc_assert (word & 1); 630#endif 631 return bit_no; 632} 633 634 635/* DST = A & B. */ 636 637void 638bitmap_and (bitmap dst, bitmap a, bitmap b) 639{ 640 bitmap_element *dst_elt = dst->first; 641 bitmap_element *a_elt = a->first; 642 bitmap_element *b_elt = b->first; 643 bitmap_element *dst_prev = NULL; 644 645 gcc_assert (dst != a && dst != b); 646 647 if (a == b) 648 { 649 bitmap_copy (dst, a); 650 return; 651 } 652 653 while (a_elt && b_elt) 654 { 655 if (a_elt->indx < b_elt->indx) 656 a_elt = a_elt->next; 657 else if (b_elt->indx < a_elt->indx) 658 b_elt = b_elt->next; 659 else 660 { 661 /* Matching elts, generate A & B. */ 662 unsigned ix; 663 BITMAP_WORD ior = 0; 664 665 if (!dst_elt) 666 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 667 else 668 dst_elt->indx = a_elt->indx; 669 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 670 { 671 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 672 673 dst_elt->bits[ix] = r; 674 ior |= r; 675 } 676 if (ior) 677 { 678 dst_prev = dst_elt; 679 dst_elt = dst_elt->next; 680 } 681 a_elt = a_elt->next; 682 b_elt = b_elt->next; 683 } 684 } 685 bitmap_elt_clear_from (dst, dst_elt); 686 gcc_assert (!dst->current == !dst->first); 687 if (dst->current) 688 dst->indx = dst->current->indx; 689} 690 691/* A &= B. */ 692 693void 694bitmap_and_into (bitmap a, bitmap b) 695{ 696 bitmap_element *a_elt = a->first; 697 bitmap_element *b_elt = b->first; 698 bitmap_element *next; 699 700 if (a == b) 701 return; 702 703 while (a_elt && b_elt) 704 { 705 if (a_elt->indx < b_elt->indx) 706 { 707 next = a_elt->next; 708 bitmap_element_free (a, a_elt); 709 a_elt = next; 710 } 711 else if (b_elt->indx < a_elt->indx) 712 b_elt = b_elt->next; 713 else 714 { 715 /* Matching elts, generate A &= B. */ 716 unsigned ix; 717 BITMAP_WORD ior = 0; 718 719 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 720 { 721 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 722 723 a_elt->bits[ix] = r; 724 ior |= r; 725 } 726 next = a_elt->next; 727 if (!ior) 728 bitmap_element_free (a, a_elt); 729 a_elt = next; 730 b_elt = b_elt->next; 731 } 732 } 733 bitmap_elt_clear_from (a, a_elt); 734 gcc_assert (!a->current == !a->first); 735 gcc_assert (!a->current || a->indx == a->current->indx); 736} 737 738/* DST = A & ~B */ 739 740void 741bitmap_and_compl (bitmap dst, bitmap a, bitmap b) 742{ 743 bitmap_element *dst_elt = dst->first; 744 bitmap_element *a_elt = a->first; 745 bitmap_element *b_elt = b->first; 746 bitmap_element *dst_prev = NULL; 747 748 gcc_assert (dst != a && dst != b); 749 750 if (a == b) 751 { 752 bitmap_clear (dst); 753 return; 754 } 755 756 while (a_elt) 757 { 758 if (!b_elt || a_elt->indx < b_elt->indx) 759 { 760 /* Copy a_elt. */ 761 if (!dst_elt) 762 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 763 else 764 dst_elt->indx = a_elt->indx; 765 memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits)); 766 dst_prev = dst_elt; 767 dst_elt = dst_elt->next; 768 a_elt = a_elt->next; 769 } 770 else if (b_elt->indx < a_elt->indx) 771 b_elt = b_elt->next; 772 else 773 { 774 /* Matching elts, generate A & ~B. */ 775 unsigned ix; 776 BITMAP_WORD ior = 0; 777 778 if (!dst_elt) 779 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 780 else 781 dst_elt->indx = a_elt->indx; 782 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 783 { 784 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; 785 786 dst_elt->bits[ix] = r; 787 ior |= r; 788 } 789 if (ior) 790 { 791 dst_prev = dst_elt; 792 dst_elt = dst_elt->next; 793 } 794 a_elt = a_elt->next; 795 b_elt = b_elt->next; 796 } 797 } 798 bitmap_elt_clear_from (dst, dst_elt); 799 gcc_assert (!dst->current == !dst->first); 800 if (dst->current) 801 dst->indx = dst->current->indx; 802} 803 804/* A &= ~B. Returns true if A changes */ 805 806bool 807bitmap_and_compl_into (bitmap a, bitmap b) 808{ 809 bitmap_element *a_elt = a->first; 810 bitmap_element *b_elt = b->first; 811 bitmap_element *next; 812 BITMAP_WORD changed = 0; 813 814 if (a == b) 815 { 816 if (bitmap_empty_p (a)) 817 return false; 818 else 819 { 820 bitmap_clear (a); 821 return true; 822 } 823 } 824 825 while (a_elt && b_elt) 826 { 827 if (a_elt->indx < b_elt->indx) 828 a_elt = a_elt->next; 829 else if (b_elt->indx < a_elt->indx) 830 b_elt = b_elt->next; 831 else 832 { 833 /* Matching elts, generate A &= ~B. */ 834 unsigned ix; 835 BITMAP_WORD ior = 0; 836 837 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 838 { 839 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 840 BITMAP_WORD r = a_elt->bits[ix] ^ cleared; 841 842 a_elt->bits[ix] = r; 843 changed |= cleared; 844 ior |= r; 845 } 846 next = a_elt->next; 847 if (!ior) 848 bitmap_element_free (a, a_elt); 849 a_elt = next; 850 b_elt = b_elt->next; 851 } 852 } 853 gcc_assert (!a->current == !a->first); 854 gcc_assert (!a->current || a->indx == a->current->indx); 855 return changed != 0; 856} 857 858/* Clear COUNT bits from START in HEAD. */ 859void 860bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) 861{ 862 unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS; 863 unsigned int end_bit_plus1 = start + count; 864 unsigned int end_bit = end_bit_plus1 - 1; 865 unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS; 866 bitmap_element *elt = bitmap_find_bit (head, start); 867 868 /* If bitmap_find_bit returns zero, the current is the closest block 869 to the result. If the current is less than first index, find the 870 next one. Otherwise, just set elt to be current. */ 871 if (!elt) 872 { 873 if (head->current) 874 { 875 if (head->indx < first_index) 876 { 877 elt = head->current->next; 878 if (!elt) 879 return; 880 } 881 else 882 elt = head->current; 883 } 884 else 885 return; 886 } 887 888 while (elt && (elt->indx <= last_index)) 889 { 890 bitmap_element * next_elt = elt->next; 891 unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; 892 unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; 893 894 895 if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) 896 /* Get rid of the entire elt and go to the next one. */ 897 bitmap_element_free (head, elt); 898 else 899 { 900 /* Going to have to knock out some bits in this elt. */ 901 unsigned int first_word_to_mod; 902 BITMAP_WORD first_mask; 903 unsigned int last_word_to_mod; 904 BITMAP_WORD last_mask; 905 unsigned int i; 906 bool clear = true; 907 908 if (elt_start_bit <= start) 909 { 910 /* The first bit to turn off is somewhere inside this 911 elt. */ 912 first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; 913 914 /* This mask should have 1s in all bits >= start position. */ 915 first_mask = 916 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; 917 first_mask = ~first_mask; 918 } 919 else 920 { 921 /* The first bit to turn off is below this start of this elt. */ 922 first_word_to_mod = 0; 923 first_mask = 0; 924 first_mask = ~first_mask; 925 } 926 927 if (elt_end_bit_plus1 <= end_bit_plus1) 928 { 929 /* The last bit to turn off is beyond this elt. */ 930 last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; 931 last_mask = 0; 932 last_mask = ~last_mask; 933 } 934 else 935 { 936 /* The last bit to turn off is inside to this elt. */ 937 last_word_to_mod = 938 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; 939 940 /* The last mask should have 1s below the end bit. */ 941 last_mask = 942 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; 943 } 944 945 946 if (first_word_to_mod == last_word_to_mod) 947 { 948 BITMAP_WORD mask = first_mask & last_mask; 949 elt->bits[first_word_to_mod] &= ~mask; 950 } 951 else 952 { 953 elt->bits[first_word_to_mod] &= ~first_mask; 954 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) 955 elt->bits[i] = 0; 956 elt->bits[last_word_to_mod] &= ~last_mask; 957 } 958 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 959 if (elt->bits[i]) 960 { 961 clear = false; 962 break; 963 } 964 /* Check to see if there are any bits left. */ 965 if (clear) 966 bitmap_element_free (head, elt); 967 } 968 elt = next_elt; 969 } 970 971 if (elt) 972 { 973 head->current = elt; 974 head->indx = head->current->indx; 975 } 976} 977 978/* A = ~A & B. */ 979 980void 981bitmap_compl_and_into (bitmap a, bitmap b) 982{ 983 bitmap_element *a_elt = a->first; 984 bitmap_element *b_elt = b->first; 985 bitmap_element *a_prev = NULL; 986 bitmap_element *next; 987 988 gcc_assert (a != b); 989 990 if (bitmap_empty_p (a)) 991 { 992 bitmap_copy (a, b); 993 return; 994 } 995 if (bitmap_empty_p (b)) 996 { 997 bitmap_clear (a); 998 return; 999 } 1000 1001 while (a_elt || b_elt) 1002 { 1003 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1004 { 1005 /* A is before B. Remove A */ 1006 next = a_elt->next; 1007 a_prev = a_elt->prev; 1008 bitmap_element_free (a, a_elt); 1009 a_elt = next; 1010 } 1011 else if (!a_elt || b_elt->indx < a_elt->indx) 1012 { 1013 /* B is before A. Copy B. */ 1014 next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1015 memcpy (next->bits, b_elt->bits, sizeof (next->bits)); 1016 a_prev = next; 1017 b_elt = b_elt->next; 1018 } 1019 else 1020 { 1021 /* Matching elts, generate A = ~A & B. */ 1022 unsigned ix; 1023 BITMAP_WORD ior = 0; 1024 1025 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1026 { 1027 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 1028 BITMAP_WORD r = b_elt->bits[ix] ^ cleared; 1029 1030 a_elt->bits[ix] = r; 1031 ior |= r; 1032 } 1033 next = a_elt->next; 1034 if (!ior) 1035 bitmap_element_free (a, a_elt); 1036 else 1037 a_prev = a_elt; 1038 a_elt = next; 1039 b_elt = b_elt->next; 1040 } 1041 } 1042 gcc_assert (!a->current == !a->first); 1043 gcc_assert (!a->current || a->indx == a->current->indx); 1044 return; 1045} 1046 1047/* DST = A | B. Return true if DST changes. */ 1048 1049bool 1050bitmap_ior (bitmap dst, bitmap a, bitmap b) 1051{ 1052 bitmap_element *dst_elt = dst->first; 1053 bitmap_element *a_elt = a->first; 1054 bitmap_element *b_elt = b->first; 1055 bitmap_element *dst_prev = NULL; 1056 bool changed = false; 1057 1058 gcc_assert (dst != a && dst != b); 1059 1060 while (a_elt || b_elt) 1061 { 1062 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1063 { 1064 /* Matching elts, generate A | B. */ 1065 unsigned ix; 1066 1067 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) 1068 { 1069 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1070 { 1071 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1072 1073 if (r != dst_elt->bits[ix]) 1074 { 1075 dst_elt->bits[ix] = r; 1076 changed = true; 1077 } 1078 } 1079 } 1080 else 1081 { 1082 changed = true; 1083 if (!dst_elt) 1084 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1085 else 1086 dst_elt->indx = a_elt->indx; 1087 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1088 { 1089 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1090 1091 dst_elt->bits[ix] = r; 1092 } 1093 } 1094 a_elt = a_elt->next; 1095 b_elt = b_elt->next; 1096 dst_prev = dst_elt; 1097 dst_elt = dst_elt->next; 1098 } 1099 else 1100 { 1101 /* Copy a single element. */ 1102 bitmap_element *src; 1103 1104 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1105 { 1106 src = a_elt; 1107 a_elt = a_elt->next; 1108 } 1109 else 1110 { 1111 src = b_elt; 1112 b_elt = b_elt->next; 1113 } 1114 1115 if (!changed && dst_elt && dst_elt->indx == src->indx) 1116 { 1117 unsigned ix; 1118 1119 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1120 if (src->bits[ix] != dst_elt->bits[ix]) 1121 { 1122 dst_elt->bits[ix] = src->bits[ix]; 1123 changed = true; 1124 } 1125 } 1126 else 1127 { 1128 changed = true; 1129 if (!dst_elt) 1130 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); 1131 else 1132 dst_elt->indx = src->indx; 1133 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1134 } 1135 1136 dst_prev = dst_elt; 1137 dst_elt = dst_elt->next; 1138 } 1139 } 1140 1141 if (dst_elt) 1142 { 1143 changed = true; 1144 bitmap_elt_clear_from (dst, dst_elt); 1145 } 1146 gcc_assert (!dst->current == !dst->first); 1147 if (dst->current) 1148 dst->indx = dst->current->indx; 1149 return changed; 1150} 1151 1152/* A |= B. Return true if A changes. */ 1153 1154bool 1155bitmap_ior_into (bitmap a, bitmap b) 1156{ 1157 bitmap_element *a_elt = a->first; 1158 bitmap_element *b_elt = b->first; 1159 bitmap_element *a_prev = NULL; 1160 bool changed = false; 1161 1162 if (a == b) 1163 return false; 1164 1165 while (b_elt) 1166 { 1167 if (!a_elt || b_elt->indx < a_elt->indx) 1168 { 1169 /* Copy b_elt. */ 1170 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1171 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1172 a_prev = dst; 1173 b_elt = b_elt->next; 1174 changed = true; 1175 } 1176 else if (a_elt->indx < b_elt->indx) 1177 { 1178 a_prev = a_elt; 1179 a_elt = a_elt->next; 1180 } 1181 else 1182 { 1183 /* Matching elts, generate A |= B. */ 1184 unsigned ix; 1185 1186 if (changed) 1187 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1188 { 1189 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1190 1191 a_elt->bits[ix] = r; 1192 } 1193 else 1194 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1195 { 1196 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 1197 1198 if (a_elt->bits[ix] != r) 1199 { 1200 changed = true; 1201 a_elt->bits[ix] = r; 1202 } 1203 } 1204 b_elt = b_elt->next; 1205 a_prev = a_elt; 1206 a_elt = a_elt->next; 1207 } 1208 } 1209 gcc_assert (!a->current == !a->first); 1210 if (a->current) 1211 a->indx = a->current->indx; 1212 return changed; 1213} 1214 1215/* DST = A ^ B */ 1216 1217void 1218bitmap_xor (bitmap dst, bitmap a, bitmap b) 1219{ 1220 bitmap_element *dst_elt = dst->first; 1221 bitmap_element *a_elt = a->first; 1222 bitmap_element *b_elt = b->first; 1223 bitmap_element *dst_prev = NULL; 1224 1225 gcc_assert (dst != a && dst != b); 1226 if (a == b) 1227 { 1228 bitmap_clear (dst); 1229 return; 1230 } 1231 1232 while (a_elt || b_elt) 1233 { 1234 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 1235 { 1236 /* Matching elts, generate A ^ B. */ 1237 unsigned ix; 1238 BITMAP_WORD ior = 0; 1239 1240 if (!dst_elt) 1241 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); 1242 else 1243 dst_elt->indx = a_elt->indx; 1244 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1245 { 1246 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1247 1248 ior |= r; 1249 dst_elt->bits[ix] = r; 1250 } 1251 a_elt = a_elt->next; 1252 b_elt = b_elt->next; 1253 if (ior) 1254 { 1255 dst_prev = dst_elt; 1256 dst_elt = dst_elt->next; 1257 } 1258 } 1259 else 1260 { 1261 /* Copy a single element. */ 1262 bitmap_element *src; 1263 1264 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1265 { 1266 src = a_elt; 1267 a_elt = a_elt->next; 1268 } 1269 else 1270 { 1271 src = b_elt; 1272 b_elt = b_elt->next; 1273 } 1274 1275 if (!dst_elt) 1276 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); 1277 else 1278 dst_elt->indx = src->indx; 1279 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1280 dst_prev = dst_elt; 1281 dst_elt = dst_elt->next; 1282 } 1283 } 1284 bitmap_elt_clear_from (dst, dst_elt); 1285 gcc_assert (!dst->current == !dst->first); 1286 if (dst->current) 1287 dst->indx = dst->current->indx; 1288} 1289 1290/* A ^= B */ 1291 1292void 1293bitmap_xor_into (bitmap a, bitmap b) 1294{ 1295 bitmap_element *a_elt = a->first; 1296 bitmap_element *b_elt = b->first; 1297 bitmap_element *a_prev = NULL; 1298 1299 if (a == b) 1300 { 1301 bitmap_clear (a); 1302 return; 1303 } 1304 1305 while (b_elt) 1306 { 1307 if (!a_elt || b_elt->indx < a_elt->indx) 1308 { 1309 /* Copy b_elt. */ 1310 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); 1311 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1312 a_prev = dst; 1313 b_elt = b_elt->next; 1314 } 1315 else if (a_elt->indx < b_elt->indx) 1316 { 1317 a_prev = a_elt; 1318 a_elt = a_elt->next; 1319 } 1320 else 1321 { 1322 /* Matching elts, generate A ^= B. */ 1323 unsigned ix; 1324 BITMAP_WORD ior = 0; 1325 bitmap_element *next = a_elt->next; 1326 1327 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1328 { 1329 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1330 1331 ior |= r; 1332 a_elt->bits[ix] = r; 1333 } 1334 b_elt = b_elt->next; 1335 if (ior) 1336 a_prev = a_elt; 1337 else 1338 bitmap_element_free (a, a_elt); 1339 a_elt = next; 1340 } 1341 } 1342 gcc_assert (!a->current == !a->first); 1343 if (a->current) 1344 a->indx = a->current->indx; 1345} 1346 1347/* Return true if two bitmaps are identical. 1348 We do not bother with a check for pointer equality, as that never 1349 occurs in practice. */ 1350 1351bool 1352bitmap_equal_p (bitmap a, bitmap b) 1353{ 1354 bitmap_element *a_elt; 1355 bitmap_element *b_elt; 1356 unsigned ix; 1357 1358 for (a_elt = a->first, b_elt = b->first; 1359 a_elt && b_elt; 1360 a_elt = a_elt->next, b_elt = b_elt->next) 1361 { 1362 if (a_elt->indx != b_elt->indx) 1363 return false; 1364 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1365 if (a_elt->bits[ix] != b_elt->bits[ix]) 1366 return false; 1367 } 1368 return !a_elt && !b_elt; 1369} 1370 1371/* Return true if A AND B is not empty. */ 1372 1373bool 1374bitmap_intersect_p (bitmap a, bitmap b) 1375{ 1376 bitmap_element *a_elt; 1377 bitmap_element *b_elt; 1378 unsigned ix; 1379 1380 for (a_elt = a->first, b_elt = b->first; 1381 a_elt && b_elt;) 1382 { 1383 if (a_elt->indx < b_elt->indx) 1384 a_elt = a_elt->next; 1385 else if (b_elt->indx < a_elt->indx) 1386 b_elt = b_elt->next; 1387 else 1388 { 1389 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1390 if (a_elt->bits[ix] & b_elt->bits[ix]) 1391 return true; 1392 a_elt = a_elt->next; 1393 b_elt = b_elt->next; 1394 } 1395 } 1396 return false; 1397} 1398 1399/* Return true if A AND NOT B is not empty. */ 1400 1401bool 1402bitmap_intersect_compl_p (bitmap a, bitmap b) 1403{ 1404 bitmap_element *a_elt; 1405 bitmap_element *b_elt; 1406 unsigned ix; 1407 for (a_elt = a->first, b_elt = b->first; 1408 a_elt && b_elt;) 1409 { 1410 if (a_elt->indx < b_elt->indx) 1411 return true; 1412 else if (b_elt->indx < a_elt->indx) 1413 b_elt = b_elt->next; 1414 else 1415 { 1416 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1417 if (a_elt->bits[ix] & ~b_elt->bits[ix]) 1418 return true; 1419 a_elt = a_elt->next; 1420 b_elt = b_elt->next; 1421 } 1422 } 1423 return a_elt != NULL; 1424} 1425 1426 1427/* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ 1428 1429bool 1430bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2) 1431{ 1432 bitmap_head tmp; 1433 bool changed; 1434 1435 bitmap_initialize (&tmp, &bitmap_default_obstack); 1436 bitmap_and_compl (&tmp, from1, from2); 1437 changed = bitmap_ior (dst, a, &tmp); 1438 bitmap_clear (&tmp); 1439 1440 return changed; 1441} 1442 1443/* A |= (FROM1 & ~FROM2). Return true if A changes. */ 1444 1445bool 1446bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2) 1447{ 1448 bitmap_head tmp; 1449 bool changed; 1450 1451 bitmap_initialize (&tmp, &bitmap_default_obstack); 1452 bitmap_and_compl (&tmp, from1, from2); 1453 changed = bitmap_ior_into (a, &tmp); 1454 bitmap_clear (&tmp); 1455 1456 return changed; 1457} 1458 1459/* Debugging function to print out the contents of a bitmap. */ 1460 1461void 1462debug_bitmap_file (FILE *file, bitmap head) 1463{ 1464 bitmap_element *ptr; 1465 1466 fprintf (file, "\nfirst = %p current = %p indx = %u\n", 1467 (void *) head->first, (void *) head->current, head->indx); 1468 1469 for (ptr = head->first; ptr; ptr = ptr->next) 1470 { 1471 unsigned int i, j, col = 26; 1472 1473 fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {", 1474 (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx); 1475 1476 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 1477 for (j = 0; j < BITMAP_WORD_BITS; j++) 1478 if ((ptr->bits[i] >> j) & 1) 1479 { 1480 if (col > 70) 1481 { 1482 fprintf (file, "\n\t\t\t"); 1483 col = 24; 1484 } 1485 1486 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS 1487 + i * BITMAP_WORD_BITS + j)); 1488 col += 4; 1489 } 1490 1491 fprintf (file, " }\n"); 1492 } 1493} 1494 1495/* Function to be called from the debugger to print the contents 1496 of a bitmap. */ 1497 1498void 1499debug_bitmap (bitmap head) 1500{ 1501 debug_bitmap_file (stdout, head); 1502} 1503 1504/* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, 1505 it does not print anything but the bits. */ 1506 1507void 1508bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix) 1509{ 1510 const char *comma = ""; 1511 unsigned i; 1512 bitmap_iterator bi; 1513 1514 fputs (prefix, file); 1515 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) 1516 { 1517 fprintf (file, "%s%d", comma, i); 1518 comma = ", "; 1519 } 1520 fputs (suffix, file); 1521} 1522 1523/* Compute hash of bitmap (for purposes of hashing). */ 1524hashval_t 1525bitmap_hash (bitmap head) 1526{ 1527 bitmap_element *ptr; 1528 BITMAP_WORD hash = 0; 1529 int ix; 1530 1531 for (ptr = head->first; ptr; ptr = ptr->next) 1532 { 1533 hash ^= ptr->indx; 1534 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 1535 hash ^= ptr->bits[ix]; 1536 } 1537 return (hashval_t)hash; 1538} 1539 1540#include "gt-bitmap.h" 1541