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