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