gcc/bitmap.c

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