gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-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 */
  33 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
  34 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
  35 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
  36                                                             GC'd elements.  */
  37
  38 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
  39 static void bitmap_element_free (bitmap, bitmap_element *);
  40 static bitmap_element *bitmap_element_allocate (bitmap);
  41 static int bitmap_element_zerop (bitmap_element *);
  42 static void bitmap_element_link (bitmap, bitmap_element *);
  43 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *);
  44 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
  45 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
  46 \f
  47
  48 /* Add ELEM to the appropriate freelist.  */
  49 static inline void
  50 bitmap_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
  70 static inline void
  71 bitmap_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 \f
  96 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
  97
  98 static inline bitmap_element *
  99 bitmap_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
 147 void
 148 bitmap_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
 187 inline void
 188 bitmap_clear (bitmap head)
 189 {
 190   if (head->first)
 191     bitmap_elt_clear_from (head, head->first);
 192 }
 193 \f
 194 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
 195    the default bitmap obstack.  */
 196
 197 void
 198 bitmap_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
 218 void
 219 bitmap_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
 232 bitmap
 233 bitmap_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
 251 bitmap
 252 bitmap_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
 264 void
 265 bitmap_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 \f
 276 /* Return nonzero if all bits in an element are zero.  */
 277
 278 static inline int
 279 bitmap_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 \f
 294 /* Link the bitmap element into the current bitmap linked list.  */
 295
 296 static inline void
 297 bitmap_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
 353 static bitmap_element *
 354 bitmap_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 \f
 380 /* Copy a bitmap to another bitmap.  */
 381
 382 void
 383 bitmap_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 \f
 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
 421 static inline bitmap_element *
 422 bitmap_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 \f
 465 /* Clear a single bit in a bitmap.  */
 466
 467 void
 468 bitmap_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
 486 void
 487 bitmap_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
 507 int
 508 bitmap_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 \f
 524 /* Return the bit number of the first set bit in the bitmap.  The
 525    bitmap must be non-empty.  */
 526
 527 unsigned
 528 bitmap_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 \f
 575
 576 /* DST = A & B.  */
 577
 578 void
 579 bitmap_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
 634 void
 635 bitmap_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
 681 void
 682 bitmap_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
 747 bool
 748 bitmap_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
 801 bool
 802 bitmap_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
 904 bool
 905 bitmap_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
 969 void
 970 bitmap_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
1044 void
1045 bitmap_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
1105 bool
1106 bitmap_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
1127 bool
1128 bitmap_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
1155 bool
1156 bitmap_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 \f
1181 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1182
1183 bool
1184 bitmap_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
1199 bool
1200 bitmap_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 \f
1213 /* Debugging function to print out the contents of a bitmap.  */
1214
1215 void
1216 debug_bitmap_file (FILE *file, bitmap head)
1217 {
1218   bitmap_element *ptr;
1219
1220   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
1221            " current = " HOST_PTR_PRINTF " indx = %u\n",
1222            (void *) head->first, (void *) head->current, head->indx);
1223
1224   for (ptr = head->first; ptr; ptr = ptr->next)
1225     {
1226       unsigned int i, j, col = 26;
1227
1228       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
1229                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
1230                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1231
1232       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1233         for (j = 0; j < BITMAP_WORD_BITS; j++)
1234           if ((ptr->bits[i] >> j) & 1)
1235             {
1236               if (col > 70)
1237                 {
1238                   fprintf (file, "\n\t\t\t");
1239                   col = 24;
1240                 }
1241
1242               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1243                                      + i * BITMAP_WORD_BITS + j));
1244               col += 4;
1245             }
1246
1247       fprintf (file, " }\n");
1248     }
1249 }
1250
1251 /* Function to be called from the debugger to print the contents
1252    of a bitmap.  */
1253
1254 void
1255 debug_bitmap (bitmap head)
1256 {
1257   debug_bitmap_file (stdout, head);
1258 }
1259
1260 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1261    it does not print anything but the bits.  */
1262
1263 void
1264 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1265 {
1266   const char *comma = "";
1267   unsigned i;
1268   bitmap_iterator bi;
1269
1270   fputs (prefix, file);
1271   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1272     {
1273       fprintf (file, "%s%d", comma, i);
1274       comma = ", ";
1275     }
1276   fputs (suffix, file);
1277 }
1278
1279 #include "gt-bitmap.h"