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 *); 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 } 93 bitmap_elem_to_freelist (head, elt); 94} 95 96/* Allocate a bitmap element. The bits are cleared, but nothing else is. */ 97 98static inline bitmap_element * 99bitmap_element_allocate (bitmap head) 100{ 101 bitmap_element *element; 102 bitmap_obstack *bit_obstack = head->obstack; 103 104 if (bit_obstack) 105 { 106 element = bit_obstack->elements; 107 108 if (element) 109 /* Use up the inner list first before looking at the next 110 element of the outer list. */ 111 if (element->next) 112 { 113 bit_obstack->elements = element->next; 114 bit_obstack->elements->prev = element->prev; 115 } 116 else 117 /* Inner list was just a singleton. */ 118 bit_obstack->elements = element->prev; 119 else 120 element = XOBNEW (&bit_obstack->obstack, bitmap_element); 121 } 122 else 123 { 124 element = bitmap_ggc_free; 125 if (element) 126 /* Use up the inner list first before looking at the next 127 element of the outer list. */ 128 if (element->next) 129 { 130 bitmap_ggc_free = element->next; 131 bitmap_ggc_free->prev = element->prev; 132 } 133 else 134 /* Inner list was just a singleton. */ 135 bitmap_ggc_free = element->prev; 136 else 137 element = GGC_NEW (bitmap_element); 138 } 139 140 memset (element->bits, 0, sizeof (element->bits)); 141 142 return element; 143} 144 145/* Remove ELT and all following elements from bitmap HEAD. */ 146 147void 148bitmap_elt_clear_from (bitmap head, bitmap_element *elt) 149{ 150 bitmap_element *prev; 151 bitmap_obstack *bit_obstack = head->obstack; 152 153 if (!elt) return; 154 155 prev = elt->prev; 156 if (prev) 157 { 158 prev->next = NULL; 159 if (head->current->indx > prev->indx) 160 { 161 head->current = prev; 162 head->indx = prev->indx; 163 } 164 } 165 else 166 { 167 head->first = NULL; 168 head->current = NULL; 169 head->indx = 0; 170 } 171 172 /* Put the entire list onto the free list in one operation. */ 173 if (bit_obstack) 174 { 175 elt->prev = bit_obstack->elements; 176 bit_obstack->elements = elt; 177 } 178 else 179 { 180 elt->prev = bitmap_ggc_free; 181 bitmap_ggc_free = elt; 182 } 183} 184 185/* Clear a bitmap by freeing the linked list. */ 186 187inline void 188bitmap_clear (bitmap head) 189{ 190 if (head->first) 191 bitmap_elt_clear_from (head, head->first); 192} 193 194/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize 195 the default bitmap obstack. */ 196 197void 198bitmap_obstack_initialize (bitmap_obstack *bit_obstack) 199{ 200 if (!bit_obstack) 201 bit_obstack = &bitmap_default_obstack; 202 203#if !defined(__GNUC__) || (__GNUC__ < 2) 204#define __alignof__(type) 0 205#endif 206 207 bit_obstack->elements = NULL; 208 bit_obstack->heads = NULL; 209 obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, 210 __alignof__ (bitmap_element), 211 obstack_chunk_alloc, 212 obstack_chunk_free); 213} 214 215/* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, 216 release the default bitmap obstack. */ 217 218void 219bitmap_obstack_release (bitmap_obstack *bit_obstack) 220{ 221 if (!bit_obstack) 222 bit_obstack = &bitmap_default_obstack; 223 224 bit_obstack->elements = NULL; 225 bit_obstack->heads = NULL; 226 obstack_free (&bit_obstack->obstack, NULL); 227} 228 229/* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create 230 it on the default bitmap obstack. */ 231 232bitmap 233bitmap_obstack_alloc (bitmap_obstack *bit_obstack) 234{ 235 bitmap map; 236 237 if (!bit_obstack) 238 bit_obstack = &bitmap_default_obstack; 239 map = bit_obstack->heads; 240 if (map) 241 bit_obstack->heads = (void *)map->first; 242 else 243 map = XOBNEW (&bit_obstack->obstack, bitmap_head); 244 bitmap_initialize (map, bit_obstack); 245 246 return map; 247} 248 249/* Create a new GCd bitmap. */ 250 251bitmap 252bitmap_gc_alloc (void) 253{ 254 bitmap map; 255 256 map = GGC_NEW (struct bitmap_head_def); 257 bitmap_initialize (map, NULL); 258 259 return map; 260} 261 262/* Release an obstack allocated bitmap. */ 263 264void 265bitmap_obstack_free (bitmap map) 266{ 267 if (map) 268 { 269 bitmap_clear (map); 270 map->first = (void *)map->obstack->heads; 271 map->obstack->heads = map; 272 } 273} 274 275 276/* Return nonzero if all bits in an element are zero. */ 277 278static inline int 279bitmap_element_zerop (bitmap_element *element) 280{ 281#if BITMAP_ELEMENT_WORDS == 2 282 return (element->bits[0] | element->bits[1]) == 0; 283#else 284 unsigned i; 285 286 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 287 if (element->bits[i] != 0) 288 return 0; 289 290 return 1; 291#endif 292} 293 294/* Link the bitmap element into the current bitmap linked list. */ 295 296static inline void 297bitmap_element_link (bitmap head, bitmap_element *element) 298{ 299 unsigned int indx = element->indx; 300 bitmap_element *ptr; 301 302 /* If this is the first and only element, set it in. */ 303 if (head->first == 0) 304 { 305 element->next = element->prev = 0; 306 head->first = element; 307 } 308 309 /* If this index is less than that of the current element, it goes someplace 310 before the current element. */ 311 else if (indx < head->indx) 312 { 313 for (ptr = head->current; 314 ptr->prev != 0 && ptr->prev->indx > indx; 315 ptr = ptr->prev) 316 ; 317 318 if (ptr->prev) 319 ptr->prev->next = element; 320 else 321 head->first = element; 322 323 element->prev = ptr->prev; 324 element->next = ptr; 325 ptr->prev = element; 326 } 327 328 /* Otherwise, it must go someplace after the current element. */ 329 else 330 { 331 for (ptr = head->current; 332 ptr->next != 0 && ptr->next->indx < indx; 333 ptr = ptr->next) 334 ; 335 336 if (ptr->next) 337 ptr->next->prev = element; 338 339 element->next = ptr->next; 340 element->prev = ptr; 341 ptr->next = element; 342 } 343 344 /* Set up so this is the first element searched. */ 345 head->current = element; 346 head->indx = indx; 347} 348 349/* Insert a new uninitialized element into bitmap HEAD after element 350 ELT. If ELT is NULL, insert the element at the start. Return the 351 new element. */ 352 353static bitmap_element * 354bitmap_elt_insert_after (bitmap head, bitmap_element *elt) 355{ 356 bitmap_element *node = bitmap_element_allocate (head); 357 358 if (!elt) 359 { 360 if (!head->current) 361 head->current = node; 362 node->next = head->first; 363 if (node->next) 364 node->next->prev = node; 365 head->first = node; 366 node->prev = NULL; 367 } 368 else 369 { 370 gcc_assert (head->current); 371 node->next = elt->next; 372 if (node->next) 373 node->next->prev = node; 374 elt->next = node; 375 node->prev = elt; 376 } 377 return node; 378} 379 380/* Copy a bitmap to another bitmap. */ 381 382void 383bitmap_copy (bitmap to, bitmap from) 384{ 385 bitmap_element *from_ptr, *to_ptr = 0; 386 387 bitmap_clear (to); 388 389 /* Copy elements in forward direction one at a time. */ 390 for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) 391 { 392 bitmap_element *to_elt = bitmap_element_allocate (to); 393 394 to_elt->indx = from_ptr->indx; 395 memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); 396 397 /* Here we have a special case of bitmap_element_link, for the case 398 where we know the links are being entered in sequence. */ 399 if (to_ptr == 0) 400 { 401 to->first = to->current = to_elt; 402 to->indx = from_ptr->indx; 403 to_elt->next = to_elt->prev = 0; 404 } 405 else 406 { 407 to_elt->prev = to_ptr; 408 to_elt->next = 0; 409 to_ptr->next = to_elt; 410 } 411 412 to_ptr = to_elt; 413 } 414} 415 416/* Find a bitmap element that would hold a bitmap's bit. 417 Update the `current' field even if we can't find an element that 418 would hold the bitmap's bit to make eventual allocation 419 faster. */ 420 421static inline bitmap_element * 422bitmap_find_bit (bitmap head, unsigned int bit) 423{ 424 bitmap_element *element; 425 unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; 426 427 if (head->current == 0 428 || head->indx == indx) 429 return head->current; 430 431 if (head->indx < indx) 432 /* INDX is beyond head->indx. Search from head->current 433 forward. */ 434 for (element = head->current; 435 element->next != 0 && element->indx < indx; 436 element = element->next) 437 ; 438 439 else if (head->indx / 2 < indx) 440 /* INDX is less than head->indx and closer to head->indx than to 441 0. Search from head->current backward. */ 442 for (element = head->current; 443 element->prev != 0 && element->indx > indx; 444 element = element->prev) 445 ; 446 447 else 448 /* INDX is less than head->indx and closer to 0 than to 449 head->indx. Search from head->first forward. */ 450 for (element = head->first; 451 element->next != 0 && element->indx < indx; 452 element = element->next) 453 ; 454 455 /* `element' is the nearest to the one we want. If it's not the one we 456 want, the one we want doesn't exist. */ 457 head->current = element; 458 head->indx = element->indx; 459 if (element != 0 && element->indx != indx) 460 element = 0; 461 462 return element; 463} 464 465/* Clear a single bit in a bitmap. */ 466 467void 468bitmap_clear_bit (bitmap head, int bit) 469{ 470 bitmap_element *ptr = bitmap_find_bit (head, bit); 471 472 if (ptr != 0) 473 { 474 unsigned bit_num = bit % BITMAP_WORD_BITS; 475 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 476 ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num); 477 478 /* If we cleared the entire word, free up the element. */ 479 if (bitmap_element_zerop (ptr)) 480 bitmap_element_free (head, ptr); 481 } 482} 483 484/* Set a single bit in a bitmap. */ 485 486void 487bitmap_set_bit (bitmap head, int bit) 488{ 489 bitmap_element *ptr = bitmap_find_bit (head, bit); 490 unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 491 unsigned bit_num = bit % BITMAP_WORD_BITS; 492 BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; 493 494 if (ptr == 0) 495 { 496 ptr = bitmap_element_allocate (head); 497 ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; 498 ptr->bits[word_num] = bit_val; 499 bitmap_element_link (head, ptr); 500 } 501 else 502 ptr->bits[word_num] |= bit_val; 503} 504 505/* Return whether a bit is set within a bitmap. */ 506 507int 508bitmap_bit_p (bitmap head, int bit) 509{ 510 bitmap_element *ptr; 511 unsigned bit_num; 512 unsigned word_num; 513 514 ptr = bitmap_find_bit (head, bit); 515 if (ptr == 0) 516 return 0; 517 518 bit_num = bit % BITMAP_WORD_BITS; 519 word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 520 521 return (ptr->bits[word_num] >> bit_num) & 1; 522} 523 524/* Return the bit number of the first set bit in the bitmap. The 525 bitmap must be non-empty. */ 526 527unsigned 528bitmap_first_set_bit (bitmap a) 529{ 530 bitmap_element *elt = a->first; 531 unsigned bit_no; 532 BITMAP_WORD word; 533 unsigned ix; 534 535 gcc_assert (elt); 536 bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; 537 for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) 538 { 539 word = elt->bits[ix]; 540 if (word) 541 goto found_bit; 542 } 543 gcc_unreachable (); 544 found_bit: 545 bit_no += ix * BITMAP_WORD_BITS; 546 547#if GCC_VERSION >= 3004 548 gcc_assert (sizeof(long) == sizeof (word)); 549 bit_no += __builtin_ctzl (word); 550#else 551 /* Binary search for the first set bit. */ 552#if BITMAP_WORD_BITS > 64 553#error "Fill out the table." 554#endif 555#if BITMAP_WORD_BITS > 32 556 if (!(word & 0xffffffff)) 557 word >>= 32, bit_no += 32; 558#endif 559 if (!(word & 0xffff)) 560 word >>= 16, bit_no += 16; 561 if (!(word & 0xff)) 562 word >>= 8, bit_no += 8; 563 if (!(word & 0xf)) 564 word >>= 4, bit_no += 4; 565 if (!(word & 0x3)) 566 word >>= 2, bit_no += 2; 567 if (!(word & 0x1)) 568 word >>= 1, bit_no += 1; 569 570 gcc_assert (word & 1); 571#endif 572 return bit_no; 573} 574 575 576/* DST = A & B. */ 577 578void 579bitmap_and (bitmap dst, bitmap a, bitmap b) 580{ 581 bitmap_element *dst_elt = dst->first; 582 bitmap_element *a_elt = a->first; 583 bitmap_element *b_elt = b->first; 584 bitmap_element *dst_prev = NULL; 585 586 gcc_assert (dst != a && dst != b); 587 588 if (a == b) 589 { 590 bitmap_copy (dst, a); 591 return; 592 } 593 594 while (a_elt && b_elt) 595 { 596 if (a_elt->indx < b_elt->indx) 597 a_elt = a_elt->next; 598 else if (b_elt->indx < a_elt->indx) 599 b_elt = b_elt->next; 600 else 601 { 602 /* Matching elts, generate A & B. */ 603 unsigned ix; 604 BITMAP_WORD ior = 0; 605 606 if (!dst_elt) 607 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 608 609 dst_elt->indx = a_elt->indx; 610 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 611 { 612 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 613 614 dst_elt->bits[ix] = r; 615 ior |= r; 616 } 617 if (ior) 618 { 619 dst_prev = dst_elt; 620 dst_elt = dst_elt->next; 621 } 622 a_elt = a_elt->next; 623 b_elt = b_elt->next; 624 } 625 } 626 bitmap_elt_clear_from (dst, dst_elt); 627 gcc_assert (!dst->current == !dst->first); 628 if (dst->current) 629 dst->indx = dst->current->indx; 630} 631 632/* A &= B. */ 633 634void 635bitmap_and_into (bitmap a, bitmap b) 636{ 637 bitmap_element *a_elt = a->first; 638 bitmap_element *b_elt = b->first; 639 bitmap_element *next; 640 641 if (a == b) 642 return; 643 644 while (a_elt && b_elt) 645 { 646 if (a_elt->indx < b_elt->indx) 647 { 648 next = a_elt->next; 649 bitmap_element_free (a, a_elt); 650 a_elt = next; 651 } 652 else if (b_elt->indx < a_elt->indx) 653 b_elt = b_elt->next; 654 else 655 { 656 /* Matching elts, generate A &= B. */ 657 unsigned ix; 658 BITMAP_WORD ior = 0; 659 660 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 661 { 662 BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; 663 664 a_elt->bits[ix] = r; 665 ior |= r; 666 } 667 next = a_elt->next; 668 if (!ior) 669 bitmap_element_free (a, a_elt); 670 a_elt = next; 671 b_elt = b_elt->next; 672 } 673 } 674 bitmap_elt_clear_from (a, a_elt); 675 gcc_assert (!a->current == !a->first); 676 gcc_assert (!a->current || a->indx == a->current->indx); 677} 678 679/* DST = A & ~B */ 680 681void 682bitmap_and_compl (bitmap dst, bitmap a, bitmap b) 683{ 684 bitmap_element *dst_elt = dst->first; 685 bitmap_element *a_elt = a->first; 686 bitmap_element *b_elt = b->first; 687 bitmap_element *dst_prev = NULL; 688 689 gcc_assert (dst != a && dst != b); 690 691 if (a == b) 692 { 693 bitmap_clear (dst); 694 return; 695 } 696 697 while (a_elt) 698 { 699 if (!b_elt || a_elt->indx < b_elt->indx) 700 { 701 /* Copy a_elt. */ 702 if (!dst_elt) 703 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 704 705 dst_elt->indx = a_elt->indx; 706 memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits)); 707 dst_prev = dst_elt; 708 dst_elt = dst_elt->next; 709 a_elt = 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 if (!dst_elt) 720 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 721 722 dst_elt->indx = a_elt->indx; 723 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 724 { 725 BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; 726 727 dst_elt->bits[ix] = r; 728 ior |= r; 729 } 730 if (ior) 731 { 732 dst_prev = dst_elt; 733 dst_elt = dst_elt->next; 734 } 735 a_elt = a_elt->next; 736 b_elt = b_elt->next; 737 } 738 } 739 bitmap_elt_clear_from (dst, dst_elt); 740 gcc_assert (!dst->current == !dst->first); 741 if (dst->current) 742 dst->indx = dst->current->indx; 743} 744 745/* A &= ~B. Returns true if A changes */ 746 747bool 748bitmap_and_compl_into (bitmap a, bitmap b) 749{ 750 bitmap_element *a_elt = a->first; 751 bitmap_element *b_elt = b->first; 752 bitmap_element *next; 753 BITMAP_WORD changed = 0; 754 755 if (a == b) 756 { 757 if (bitmap_empty_p (a)) 758 return false; 759 else 760 { 761 bitmap_clear (a); 762 return true; 763 } 764 } 765 766 while (a_elt && b_elt) 767 { 768 if (a_elt->indx < b_elt->indx) 769 a_elt = a_elt->next; 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 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 779 { 780 BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; 781 BITMAP_WORD r = a_elt->bits[ix] ^ cleared; 782 783 a_elt->bits[ix] = r; 784 changed |= cleared; 785 ior |= r; 786 } 787 next = a_elt->next; 788 if (!ior) 789 bitmap_element_free (a, a_elt); 790 a_elt = next; 791 b_elt = b_elt->next; 792 } 793 } 794 gcc_assert (!a->current == !a->first); 795 gcc_assert (!a->current || a->indx == a->current->indx); 796 return changed != 0; 797} 798 799/* DST = A | B. Return true if DST changes. */ 800 801bool 802bitmap_ior (bitmap dst, bitmap a, bitmap b) 803{ 804 bitmap_element *dst_elt = dst->first; 805 bitmap_element *a_elt = a->first; 806 bitmap_element *b_elt = b->first; 807 bitmap_element *dst_prev = NULL; 808 bool changed = false; 809 810 gcc_assert (dst != a && dst != b); 811 812 while (a_elt || b_elt) 813 { 814 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 815 { 816 /* Matching elts, generate A | B. */ 817 unsigned ix; 818 819 if (!changed && dst_elt && dst_elt->indx == a_elt->indx) 820 { 821 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 822 { 823 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 824 825 if (r != dst_elt->bits[ix]) 826 { 827 dst_elt->bits[ix] = r; 828 changed = true; 829 } 830 } 831 } 832 else 833 { 834 changed = true; 835 if (!dst_elt) 836 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 837 dst_elt->indx = a_elt->indx; 838 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 839 { 840 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 841 842 dst_elt->bits[ix] = r; 843 } 844 } 845 a_elt = a_elt->next; 846 b_elt = b_elt->next; 847 dst_prev = dst_elt; 848 dst_elt = dst_elt->next; 849 } 850 else 851 { 852 /* Copy a single element. */ 853 bitmap_element *src; 854 855 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 856 { 857 src = a_elt; 858 a_elt = a_elt->next; 859 } 860 else 861 { 862 src = b_elt; 863 b_elt = b_elt->next; 864 } 865 866 if (!changed && dst_elt && dst_elt->indx == src->indx) 867 { 868 unsigned ix; 869 870 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 871 if (src->bits[ix] != dst_elt->bits[ix]) 872 { 873 dst_elt->bits[ix] = src->bits[ix]; 874 changed = true; 875 } 876 } 877 else 878 { 879 changed = true; 880 if (!dst_elt) 881 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 882 dst_elt->indx = src->indx; 883 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 884 } 885 886 dst_prev = dst_elt; 887 dst_elt = dst_elt->next; 888 } 889 } 890 891 if (dst_elt) 892 { 893 changed = true; 894 bitmap_elt_clear_from (dst, dst_elt); 895 } 896 gcc_assert (!dst->current == !dst->first); 897 if (dst->current) 898 dst->indx = dst->current->indx; 899 return changed; 900} 901 902/* A |= B. Return true if A changes. */ 903 904bool 905bitmap_ior_into (bitmap a, bitmap b) 906{ 907 bitmap_element *a_elt = a->first; 908 bitmap_element *b_elt = b->first; 909 bitmap_element *a_prev = NULL; 910 bool changed = false; 911 912 if (a == b) 913 return false; 914 915 while (b_elt) 916 { 917 if (!a_elt || b_elt->indx < a_elt->indx) 918 { 919 /* Copy b_elt. */ 920 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev); 921 922 dst->indx = b_elt->indx; 923 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 924 a_prev = dst; 925 b_elt = b_elt->next; 926 changed = true; 927 } 928 else if (a_elt->indx < b_elt->indx) 929 { 930 a_prev = a_elt; 931 a_elt = a_elt->next; 932 } 933 else 934 { 935 /* Matching elts, generate A |= B. */ 936 unsigned ix; 937 938 if (changed) 939 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 940 { 941 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 942 943 a_elt->bits[ix] = r; 944 } 945 else 946 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 947 { 948 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; 949 950 if (a_elt->bits[ix] != r) 951 { 952 changed = true; 953 a_elt->bits[ix] = r; 954 } 955 } 956 b_elt = b_elt->next; 957 a_prev = a_elt; 958 a_elt = a_elt->next; 959 } 960 } 961 gcc_assert (!a->current == !a->first); 962 if (a->current) 963 a->indx = a->current->indx; 964 return changed; 965} 966 967/* DST = A ^ B */ 968 969void 970bitmap_xor (bitmap dst, bitmap a, bitmap b) 971{ 972 bitmap_element *dst_elt = dst->first; 973 bitmap_element *a_elt = a->first; 974 bitmap_element *b_elt = b->first; 975 bitmap_element *dst_prev = NULL; 976 977 gcc_assert (dst != a && dst != b); 978 if (a == b) 979 { 980 bitmap_clear (dst); 981 return; 982 } 983 984 while (a_elt || b_elt) 985 { 986 if (a_elt && b_elt && a_elt->indx == b_elt->indx) 987 { 988 /* Matching elts, generate A ^ B. */ 989 unsigned ix; 990 BITMAP_WORD ior = 0; 991 992 if (!dst_elt) 993 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 994 995 dst_elt->indx = a_elt->indx; 996 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 997 { 998 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 999 1000 ior |= r; 1001 dst_elt->bits[ix] = r; 1002 } 1003 a_elt = a_elt->next; 1004 b_elt = b_elt->next; 1005 if (ior) 1006 { 1007 dst_prev = dst_elt; 1008 dst_elt = dst_elt->next; 1009 } 1010 } 1011 else 1012 { 1013 /* Copy a single element. */ 1014 bitmap_element *src; 1015 1016 if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) 1017 { 1018 src = a_elt; 1019 a_elt = a_elt->next; 1020 } 1021 else 1022 { 1023 src = b_elt; 1024 b_elt = b_elt->next; 1025 } 1026 1027 if (!dst_elt) 1028 dst_elt = bitmap_elt_insert_after (dst, dst_prev); 1029 1030 dst_elt->indx = src->indx; 1031 memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); 1032 dst_prev = dst_elt; 1033 dst_elt = dst_elt->next; 1034 } 1035 } 1036 bitmap_elt_clear_from (dst, dst_elt); 1037 gcc_assert (!dst->current == !dst->first); 1038 if (dst->current) 1039 dst->indx = dst->current->indx; 1040} 1041 1042/* A ^= B */ 1043 1044void 1045bitmap_xor_into (bitmap a, bitmap b) 1046{ 1047 bitmap_element *a_elt = a->first; 1048 bitmap_element *b_elt = b->first; 1049 bitmap_element *a_prev = NULL; 1050 1051 if (a == b) 1052 { 1053 bitmap_clear (a); 1054 return; 1055 } 1056 1057 while (b_elt) 1058 { 1059 if (!a_elt || b_elt->indx < a_elt->indx) 1060 { 1061 /* Copy b_elt. */ 1062 bitmap_element *dst = bitmap_elt_insert_after (a, a_prev); 1063 1064 dst->indx = b_elt->indx; 1065 memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); 1066 a_prev = dst; 1067 b_elt = b_elt->next; 1068 } 1069 else if (a_elt->indx < b_elt->indx) 1070 { 1071 a_prev = a_elt; 1072 a_elt = a_elt->next; 1073 } 1074 else 1075 { 1076 /* Matching elts, generate A ^= B. */ 1077 unsigned ix; 1078 BITMAP_WORD ior = 0; 1079 bitmap_element *next = a_elt->next; 1080 1081 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1082 { 1083 BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; 1084 1085 ior |= r; 1086 a_elt->bits[ix] = r; 1087 } 1088 b_elt = b_elt->next; 1089 if (ior) 1090 a_prev = a_elt; 1091 else 1092 bitmap_element_free (a, a_elt); 1093 a_elt = next; 1094 } 1095 } 1096 gcc_assert (!a->current == !a->first); 1097 if (a->current) 1098 a->indx = a->current->indx; 1099} 1100 1101/* Return true if two bitmaps are identical. 1102 We do not bother with a check for pointer equality, as that never 1103 occurs in practice. */ 1104 1105bool 1106bitmap_equal_p (bitmap a, bitmap b) 1107{ 1108 bitmap_element *a_elt; 1109 bitmap_element *b_elt; 1110 unsigned ix; 1111 1112 for (a_elt = a->first, b_elt = b->first; 1113 a_elt && b_elt; 1114 a_elt = a_elt->next, b_elt = b_elt->next) 1115 { 1116 if (a_elt->indx != b_elt->indx) 1117 return false; 1118 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1119 if (a_elt->bits[ix] != b_elt->bits[ix]) 1120 return false; 1121 } 1122 return !a_elt && !b_elt; 1123} 1124 1125/* Return true if A AND B is not empty. */ 1126 1127bool 1128bitmap_intersect_p (bitmap a, bitmap b) 1129{ 1130 bitmap_element *a_elt; 1131 bitmap_element *b_elt; 1132 unsigned ix; 1133 1134 for (a_elt = a->first, b_elt = b->first; 1135 a_elt && b_elt;) 1136 { 1137 if (a_elt->indx < b_elt->indx) 1138 a_elt = a_elt->next; 1139 else if (b_elt->indx < a_elt->indx) 1140 b_elt = b_elt->next; 1141 else 1142 { 1143 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1144 if (a_elt->bits[ix] & b_elt->bits[ix]) 1145 return true; 1146 a_elt = a_elt->next; 1147 b_elt = b_elt->next; 1148 } 1149 } 1150 return false; 1151} 1152 1153/* Return true if A AND NOT B is not empty. */ 1154 1155bool 1156bitmap_intersect_compl_p (bitmap a, bitmap b) 1157{ 1158 bitmap_element *a_elt; 1159 bitmap_element *b_elt; 1160 unsigned ix; 1161 for (a_elt = a->first, b_elt = b->first; 1162 a_elt && b_elt;) 1163 { 1164 if (a_elt->indx < b_elt->indx) 1165 return true; 1166 else if (b_elt->indx < a_elt->indx) 1167 b_elt = b_elt->next; 1168 else 1169 { 1170 for (ix = BITMAP_ELEMENT_WORDS; ix--;) 1171 if (a_elt->bits[ix] & ~b_elt->bits[ix]) 1172 return true; 1173 a_elt = a_elt->next; 1174 b_elt = b_elt->next; 1175 } 1176 } 1177 return a_elt != NULL; 1178} 1179 1180 1181/* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ 1182 1183bool 1184bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2) 1185{ 1186 bitmap_head tmp; 1187 bool changed; 1188 1189 bitmap_initialize (&tmp, &bitmap_default_obstack); 1190 bitmap_and_compl (&tmp, from1, from2); 1191 changed = bitmap_ior (dst, a, &tmp); 1192 bitmap_clear (&tmp); 1193 1194 return changed; 1195} 1196 1197/* A |= (FROM1 & ~FROM2). Return true if A changes. */ 1198 1199bool 1200bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2) 1201{ 1202 bitmap_head tmp; 1203 bool changed; 1204 1205 bitmap_initialize (&tmp, &bitmap_default_obstack); 1206 bitmap_and_compl (&tmp, from1, from2); 1207 changed = bitmap_ior_into (a, &tmp); 1208 bitmap_clear (&tmp); 1209 1210 return changed; 1211} 1212 1213/* Debugging function to print out the contents of a bitmap. */ 1214 1215void 1216debug_bitmap_file (FILE *file, bitmap head) 1217{ 1218 bitmap_element *ptr; 1219 1220 fprintf (file, "\nfirst = %p current = %p indx = %u\n", 1221 (void *) head->first, (void *) head->current, head->indx); 1222 1223 for (ptr = head->first; ptr; ptr = ptr->next) 1224 { 1225 unsigned int i, j, col = 26; 1226 1227 fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {", 1228 (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx); 1229 1230 for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) 1231 for (j = 0; j < BITMAP_WORD_BITS; j++) 1232 if ((ptr->bits[i] >> j) & 1) 1233 { 1234 if (col > 70) 1235 { 1236 fprintf (file, "\n\t\t\t"); 1237 col = 24; 1238 } 1239 1240 fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS 1241 + i * BITMAP_WORD_BITS + j)); 1242 col += 4; 1243 } 1244 1245 fprintf (file, " }\n"); 1246 } 1247} 1248 1249/* Function to be called from the debugger to print the contents 1250 of a bitmap. */ 1251 1252void 1253debug_bitmap (bitmap head) 1254{ 1255 debug_bitmap_file (stdout, head); 1256} 1257 1258/* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, 1259 it does not print anything but the bits. */ 1260 1261void 1262bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix) 1263{ 1264 const char *comma = ""; 1265 unsigned i; 1266 bitmap_iterator bi; 1267 1268 fputs (prefix, file); 1269 EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) 1270 { 1271 fprintf (file, "%s%d", comma, i); 1272 comma = ", "; 1273 } 1274 fputs (suffix, file); 1275} 1276 1277#include "gt-bitmap.h" 1278