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   int 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   int 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, or -1
 448    if the bitmap is empty.  */
 449
 450 int
 451 bitmap_first_set_bit (bitmap a)
 452 {
 453   bitmap_element *ptr = a->first;
 454   BITMAP_WORD word;
 455   unsigned word_num, bit_num;
 456
 457   if (ptr == NULL)
 458     return -1;
 459
 460 #if BITMAP_ELEMENT_WORDS == 2
 461   word_num = 0, word = ptr->bits[0];
 462   if (word == 0)
 463     word_num = 1, word = ptr->bits[1];
 464 #else
 465   for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
 466     if ((word = ptr->bits[word_num]) != 0)
 467       goto word_found;
 468   gcc_unreachable ();
 469  word_found:
 470 #endif
 471
 472   /* Binary search for the first set bit.  */
 473   /* ??? It'd be nice to know if ffs or ffsl was available.  */
 474
 475   bit_num = 0;
 476   word = word & -word;
 477
 478 #if nBITMAP_WORD_BITS > 64
 479  #error "Fill out the table."
 480 #endif
 481 #if nBITMAP_WORD_BITS > 32
 482   if ((word & 0xffffffff) == 0)
 483     word >>= 32, bit_num += 32;
 484 #endif
 485   if ((word & 0xffff) == 0)
 486     word >>= 16, bit_num += 16;
 487   if ((word & 0xff) == 0)
 488     word >>= 8, bit_num += 8;
 489   if (word & 0xf0)
 490     bit_num += 4;
 491   if (word & 0xcc)
 492     bit_num += 2;
 493   if (word & 0xaa)
 494     bit_num += 1;
 495
 496   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 497           + word_num * BITMAP_WORD_BITS
 498           + bit_num);
 499 }
 500
 501 /* Return the bit number of the last set bit in the bitmap, or -1
 502    if the bitmap is empty.  */
 503
 504 int
 505 bitmap_last_set_bit (bitmap a)
 506 {
 507   bitmap_element *ptr = a->first;
 508   BITMAP_WORD word;
 509   unsigned word_num, bit_num;
 510
 511   if (ptr == NULL)
 512     return -1;
 513
 514   while (ptr->next != NULL)
 515     ptr = ptr->next;
 516
 517 #if BITMAP_ELEMENT_WORDS == 2
 518   word_num = 1, word = ptr->bits[1];
 519   if (word == 0)
 520     word_num = 0, word = ptr->bits[0];
 521 #else
 522   for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
 523     if ((word = ptr->bits[word_num]) != 0)
 524       goto word_found;
 525   gcc_unreachable ();
 526  word_found:
 527 #endif
 528
 529   /* Binary search for the last set bit.  */
 530
 531   bit_num = 0;
 532 #if nBITMAP_WORD_BITS > 64
 533  #error "Fill out the table."
 534 #endif
 535 #if nBITMAP_WORD_BITS > 32
 536   if (word & ~(BITMAP_WORD)0xffffffff)
 537     word >>= 32, bit_num += 32;
 538 #endif
 539   if (word & 0xffff0000)
 540     word >>= 16, bit_num += 16;
 541   if (word & 0xff00)
 542     word >>= 8, bit_num += 8;
 543   if (word & 0xf0)
 544     word >>= 4, bit_num += 4;
 545   if (word & 0xc)
 546     word >>= 2, bit_num += 2;
 547   if (word & 0x2)
 548     bit_num += 1;
 549
 550   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 551           + word_num * BITMAP_WORD_BITS
 552           + bit_num);
 553 }
 554 \f
 555
 556 /* DST = A & B. */
 557
 558 void
 559 bitmap_and (bitmap dst, bitmap a, bitmap b)
 560 {
 561   bitmap_element *dst_elt = dst->first;
 562   bitmap_element *a_elt = a->first;
 563   bitmap_element *b_elt = b->first;
 564   bitmap_element *dst_prev = NULL;
 565
 566   gcc_assert (dst != a && dst != b && a != b);
 567   while (a_elt && b_elt)
 568     {
 569       if (a_elt->indx < b_elt->indx)
 570         a_elt = a_elt->next;
 571       else if (b_elt->indx < a_elt->indx)
 572         b_elt = b_elt->next;
 573       else
 574         {
 575           /* Matching elts, generate A & B.  */
 576           unsigned ix;
 577           BITMAP_WORD ior = 0;
 578
 579           if (!dst_elt)
 580             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 581
 582           dst_elt->indx = a_elt->indx;
 583           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 584             {
 585               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 586
 587               dst_elt->bits[ix] = r;
 588               ior |= r;
 589             }
 590           if (ior)
 591             {
 592               dst_prev = dst_elt;
 593               dst_elt = dst_elt->next;
 594             }
 595           a_elt = a_elt->next;
 596           b_elt = b_elt->next;
 597         }
 598     }
 599   bitmap_elt_clear_from (dst, dst_elt);
 600   gcc_assert (!dst->current == !dst->first);
 601   if (dst->current)
 602     dst->indx = dst->current->indx;
 603 }
 604
 605 /* A &= B.  */
 606
 607 void
 608 bitmap_and_into (bitmap a, bitmap b)
 609 {
 610   bitmap_element *a_elt = a->first;
 611   bitmap_element *b_elt = b->first;
 612   bitmap_element *next;
 613
 614   gcc_assert (a != b);
 615   while (a_elt && b_elt)
 616     {
 617       if (a_elt->indx < b_elt->indx)
 618         {
 619           next = a_elt->next;
 620           bitmap_element_free (a, a_elt);
 621           a_elt = next;
 622         }
 623       else if (b_elt->indx < a_elt->indx)
 624         b_elt = b_elt->next;
 625       else
 626         {
 627           /* Matching elts, generate A &= B.  */
 628           unsigned ix;
 629           BITMAP_WORD ior = 0;
 630
 631           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 632             {
 633               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 634
 635               a_elt->bits[ix] = r;
 636               ior |= r;
 637             }
 638           next = a_elt->next;
 639           if (!ior)
 640             bitmap_element_free (a, a_elt);
 641           a_elt = next;
 642           b_elt = b_elt->next;
 643         }
 644     }
 645   bitmap_elt_clear_from (a, a_elt);
 646   gcc_assert (!a->current == !a->first);
 647   gcc_assert (!a->current || a->indx == a->current->indx);
 648 }
 649
 650 /* DST = A & ~B  */
 651
 652 void
 653 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 654 {
 655   bitmap_element *dst_elt = dst->first;
 656   bitmap_element *a_elt = a->first;
 657   bitmap_element *b_elt = b->first;
 658   bitmap_element *dst_prev = NULL;
 659
 660   gcc_assert (dst != a && dst != b && a != b);
 661
 662   while (a_elt)
 663     {
 664       if (!b_elt || a_elt->indx < b_elt->indx)
 665         {
 666           /* Copy a_elt. */
 667           if (!dst_elt)
 668             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 669
 670           dst_elt->indx = a_elt->indx;
 671           memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 672           dst_prev = dst_elt;
 673           dst_elt = dst_elt->next;
 674           a_elt = a_elt->next;
 675         }
 676       else if (b_elt->indx < a_elt->indx)
 677         b_elt = b_elt->next;
 678       else
 679         {
 680           /* Matching elts, generate A & ~B.  */
 681           unsigned ix;
 682           BITMAP_WORD ior = 0;
 683
 684           if (!dst_elt)
 685             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 686
 687           dst_elt->indx = a_elt->indx;
 688           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 689             {
 690               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 691
 692               dst_elt->bits[ix] = r;
 693               ior |= r;
 694             }
 695           if (ior)
 696             {
 697               dst_prev = dst_elt;
 698               dst_elt = dst_elt->next;
 699             }
 700           a_elt = a_elt->next;
 701           b_elt = b_elt->next;
 702         }
 703     }
 704   bitmap_elt_clear_from (dst, dst_elt);
 705   gcc_assert (!dst->current == !dst->first);
 706   if (dst->current)
 707     dst->indx = dst->current->indx;
 708 }
 709
 710 /* A &= ~B */
 711
 712 void
 713 bitmap_and_compl_into (bitmap a, bitmap b)
 714 {
 715   bitmap_element *a_elt = a->first;
 716   bitmap_element *b_elt = b->first;
 717   bitmap_element *next;
 718
 719   gcc_assert (a != b);
 720   while (a_elt && b_elt)
 721     {
 722       if (a_elt->indx < b_elt->indx)
 723         a_elt = a_elt->next;
 724       else if (b_elt->indx < a_elt->indx)
 725         b_elt = b_elt->next;
 726       else
 727         {
 728           /* Matching elts, generate A &= ~B.  */
 729           unsigned ix;
 730           BITMAP_WORD ior = 0;
 731
 732           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 733             {
 734               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 735
 736               a_elt->bits[ix] = r;
 737               ior |= r;
 738             }
 739           next = a_elt->next;
 740           if (!ior)
 741             bitmap_element_free (a, a_elt);
 742           a_elt = next;
 743           b_elt = b_elt->next;
 744         }
 745     }
 746   gcc_assert (!a->current == !a->first);
 747   gcc_assert (!a->current || a->indx == a->current->indx);
 748 }
 749
 750 /* DST = A | B.  Return true if DST changes.  */
 751
 752 bool
 753 bitmap_ior (bitmap dst, bitmap a, bitmap b)
 754 {
 755   bitmap_element *dst_elt = dst->first;
 756   bitmap_element *a_elt = a->first;
 757   bitmap_element *b_elt = b->first;
 758   bitmap_element *dst_prev = NULL;
 759   bool changed = false;
 760
 761   gcc_assert (dst != a && dst != b && a != b);
 762   while (a_elt || b_elt)
 763     {
 764       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 765         {
 766           /* Matching elts, generate A | B.  */
 767           unsigned ix;
 768
 769           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
 770             {
 771               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 772                 {
 773                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 774
 775                   if (r != dst_elt->bits[ix])
 776                     {
 777                       dst_elt->bits[ix] = r;
 778                       changed = true;
 779                     }
 780                 }
 781             }
 782           else
 783             {
 784               changed = true;
 785               if (!dst_elt)
 786                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 787               dst_elt->indx = a_elt->indx;
 788               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 789                 {
 790                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 791
 792                   dst_elt->bits[ix] = r;
 793                 }
 794             }
 795           a_elt = a_elt->next;
 796           b_elt = b_elt->next;
 797           dst_prev = dst_elt;
 798           dst_elt = dst_elt->next;
 799         }
 800       else
 801         {
 802           /* Copy a single element.  */
 803           bitmap_element *src;
 804
 805           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 806             {
 807               src = a_elt;
 808               a_elt = a_elt->next;
 809             }
 810           else
 811             {
 812               src = b_elt;
 813               b_elt = b_elt->next;
 814             }
 815
 816           if (!changed && dst_elt && dst_elt->indx == src->indx)
 817             {
 818               unsigned ix;
 819
 820               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 821                 if (src->bits[ix] != dst_elt->bits[ix])
 822                   {
 823                     dst_elt->bits[ix] = src->bits[ix];
 824                     changed = true;
 825                   }
 826             }
 827           else
 828             {
 829               changed = true;
 830               if (!dst_elt)
 831                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 832               dst_elt->indx = src->indx;
 833               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 834             }
 835
 836           dst_prev = dst_elt;
 837           dst_elt = dst_elt->next;
 838         }
 839     }
 840
 841   if (dst_elt)
 842     {
 843       changed = true;
 844       bitmap_elt_clear_from (dst, dst_elt);
 845     }
 846   gcc_assert (!dst->current == !dst->first);
 847   if (dst->current)
 848     dst->indx = dst->current->indx;
 849   return changed;
 850 }
 851
 852 /* A |= B.  Return true if A changes.  */
 853
 854 bool
 855 bitmap_ior_into (bitmap a, bitmap b)
 856 {
 857   bitmap_element *a_elt = a->first;
 858   bitmap_element *b_elt = b->first;
 859   bitmap_element *a_prev = NULL;
 860   bool changed = false;
 861
 862   gcc_assert (a != b);
 863   while (b_elt)
 864     {
 865       if (!a_elt || b_elt->indx < a_elt->indx)
 866         {
 867           /* Copy b_elt.  */
 868           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 869
 870           dst->indx = b_elt->indx;
 871           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 872           a_prev = dst;
 873           b_elt = b_elt->next;
 874           changed = true;
 875         }
 876       else if (a_elt->indx < b_elt->indx)
 877         {
 878           a_prev = a_elt;
 879           a_elt = a_elt->next;
 880         }
 881       else
 882         {
 883           /* Matching elts, generate A |= B.  */
 884           unsigned ix;
 885
 886           if (changed)
 887             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 888               {
 889                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 890
 891                 a_elt->bits[ix] = r;
 892               }
 893           else
 894             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 895               {
 896                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 897
 898                 if (a_elt->bits[ix] != r)
 899                   {
 900                     changed = true;
 901                     a_elt->bits[ix] = r;
 902                   }
 903               }
 904           b_elt = b_elt->next;
 905           a_prev = a_elt;
 906           a_elt = a_elt->next;
 907         }
 908     }
 909   gcc_assert (!a->current == !a->first);
 910   if (a->current)
 911     a->indx = a->current->indx;
 912   return changed;
 913 }
 914
 915 /* DST = A ^ B  */
 916
 917 void
 918 bitmap_xor (bitmap dst, bitmap a, bitmap b)
 919 {
 920   bitmap_element *dst_elt = dst->first;
 921   bitmap_element *a_elt = a->first;
 922   bitmap_element *b_elt = b->first;
 923   bitmap_element *dst_prev = NULL;
 924
 925   gcc_assert (dst != a && dst != b && a != b);
 926   while (a_elt || b_elt)
 927     {
 928       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 929         {
 930           /* Matching elts, generate A ^ B.  */
 931           unsigned ix;
 932           BITMAP_WORD ior = 0;
 933
 934           if (!dst_elt)
 935             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 936
 937           dst_elt->indx = a_elt->indx;
 938           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 939             {
 940               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
 941
 942               ior |= r;
 943               dst_elt->bits[ix] = r;
 944             }
 945           a_elt = a_elt->next;
 946           b_elt = b_elt->next;
 947           if (ior)
 948             {
 949               dst_prev = dst_elt;
 950               dst_elt = dst_elt->next;
 951             }
 952         }
 953       else
 954         {
 955           /* Copy a single element.  */
 956           bitmap_element *src;
 957
 958           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 959             {
 960               src = a_elt;
 961               a_elt = a_elt->next;
 962             }
 963           else
 964             {
 965               src = b_elt;
 966               b_elt = b_elt->next;
 967             }
 968
 969           if (!dst_elt)
 970             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 971
 972           dst_elt->indx = src->indx;
 973           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 974           dst_prev = dst_elt;
 975           dst_elt = dst_elt->next;
 976         }
 977     }
 978   bitmap_elt_clear_from (dst, dst_elt);
 979   gcc_assert (!dst->current == !dst->first);
 980   if (dst->current)
 981     dst->indx = dst->current->indx;
 982 }
 983
 984 /* A ^= B */
 985
 986 void
 987 bitmap_xor_into (bitmap a, bitmap b)
 988 {
 989   bitmap_element *a_elt = a->first;
 990   bitmap_element *b_elt = b->first;
 991   bitmap_element *a_prev = NULL;
 992
 993   gcc_assert (a != b);
 994   while (b_elt)
 995     {
 996       if (!a_elt || b_elt->indx < a_elt->indx)
 997         {
 998           /* Copy b_elt.  */
 999           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
1000
1001           dst->indx = b_elt->indx;
1002           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1003           a_prev = dst;
1004           b_elt = b_elt->next;
1005         }
1006       else if (a_elt->indx < b_elt->indx)
1007         {
1008           a_prev = a_elt;
1009           a_elt = a_elt->next;
1010         }
1011       else
1012         {
1013           /* Matching elts, generate A ^= B.  */
1014           unsigned ix;
1015           BITMAP_WORD ior = 0;
1016           bitmap_element *next = a_elt->next;
1017
1018           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1019             {
1020               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1021
1022               ior |= r;
1023               a_elt->bits[ix] = r;
1024             }
1025           b_elt = b_elt->next;
1026           if (ior)
1027             a_prev = a_elt;
1028           else
1029             bitmap_element_free (a, a_elt);
1030           a_elt = next;
1031         }
1032     }
1033   gcc_assert (!a->current == !a->first);
1034   if (a->current)
1035     a->indx = a->current->indx;
1036 }
1037
1038 /* Return true if two bitmaps are identical.
1039    We do not bother with a check for pointer equality, as that never
1040    occurs in practice.  */
1041
1042 bool
1043 bitmap_equal_p (bitmap a, bitmap b)
1044 {
1045   bitmap_element *a_elt;
1046   bitmap_element *b_elt;
1047   unsigned ix;
1048
1049   for (a_elt = a->first, b_elt = b->first;
1050        a_elt && b_elt;
1051        a_elt = a_elt->next, b_elt = b_elt->next)
1052     {
1053       if (a_elt->indx != b_elt->indx)
1054         return false;
1055       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1056         if (a_elt->bits[ix] != b_elt->bits[ix])
1057           return false;
1058     }
1059   return !a_elt && !b_elt;
1060 }
1061
1062 /* Return true if A AND B is not empty.  */
1063
1064 bool
1065 bitmap_intersect_p (bitmap a, bitmap b)
1066 {
1067   bitmap_element *a_elt;
1068   bitmap_element *b_elt;
1069   unsigned ix;
1070
1071   for (a_elt = a->first, b_elt = b->first;
1072        a_elt && b_elt;)
1073     {
1074       if (a_elt->indx < b_elt->indx)
1075         a_elt = a_elt->next;
1076       else if (b_elt->indx < a_elt->indx)
1077         b_elt = b_elt->next;
1078       else
1079         {
1080           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1081             if (a_elt->bits[ix] & b_elt->bits[ix])
1082               return true;
1083           a_elt = a_elt->next;
1084           b_elt = b_elt->next;
1085         }
1086     }
1087   return false;
1088 }
1089
1090 /* Return true if A AND NOT B is not empty.  */
1091
1092 bool
1093 bitmap_intersect_compl_p (bitmap a, bitmap b)
1094 {
1095   bitmap_element *a_elt;
1096   bitmap_element *b_elt;
1097   unsigned ix;
1098   for (a_elt = a->first, b_elt = b->first;
1099        a_elt && b_elt;)
1100     {
1101       if (a_elt->indx < b_elt->indx)
1102         return true;
1103       else if (b_elt->indx < a_elt->indx)
1104         b_elt = b_elt->next;
1105       else
1106         {
1107           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1108             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1109               return true;
1110           a_elt = a_elt->next;
1111           b_elt = b_elt->next;
1112         }
1113     }
1114   return a_elt != NULL;
1115 }
1116
1117 \f
1118 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1119
1120 bool
1121 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1122 {
1123   bitmap_head tmp;
1124   bool changed;
1125
1126   tmp.first = tmp.current = 0;
1127   tmp.using_obstack = 0;
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   tmp.first = tmp.current = 0;
1144   tmp.using_obstack = 0;
1145   bitmap_and_compl (&tmp, from1, from2);
1146   changed = bitmap_ior_into (a, &tmp);
1147   bitmap_clear (&tmp);
1148
1149   return changed;
1150 }
1151 \f
1152 /* Initialize a bitmap header.  */
1153
1154 bitmap
1155 bitmap_initialize (bitmap head, int using_obstack)
1156 {
1157   if (head == NULL && ! using_obstack)
1158     head = GGC_NEW (struct bitmap_head_def);
1159
1160   head->first = head->current = 0;
1161   head->using_obstack = using_obstack;
1162
1163   return head;
1164 }
1165 \f
1166 /* Debugging function to print out the contents of a bitmap.  */
1167
1168 void
1169 debug_bitmap_file (FILE *file, bitmap head)
1170 {
1171   bitmap_element *ptr;
1172
1173   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
1174            " current = " HOST_PTR_PRINTF " indx = %u\n",
1175            (void *) head->first, (void *) head->current, head->indx);
1176
1177   for (ptr = head->first; ptr; ptr = ptr->next)
1178     {
1179       unsigned int i, j, col = 26;
1180
1181       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
1182                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
1183                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1184
1185       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1186         for (j = 0; j < BITMAP_WORD_BITS; j++)
1187           if ((ptr->bits[i] >> j) & 1)
1188             {
1189               if (col > 70)
1190                 {
1191                   fprintf (file, "\n\t\t\t");
1192                   col = 24;
1193                 }
1194
1195               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1196                                      + i * BITMAP_WORD_BITS + j));
1197               col += 4;
1198             }
1199
1200       fprintf (file, " }\n");
1201     }
1202 }
1203
1204 /* Function to be called from the debugger to print the contents
1205    of a bitmap.  */
1206
1207 void
1208 debug_bitmap (bitmap head)
1209 {
1210   debug_bitmap_file (stdout, head);
1211 }
1212
1213 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1214    it does not print anything but the bits.  */
1215
1216 void
1217 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1218 {
1219   const char *comma = "";
1220   unsigned i;
1221   bitmap_iterator bi;
1222
1223   fputs (prefix, file);
1224   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1225     {
1226       fprintf (file, "%s%d", comma, i);
1227       comma = ", ";
1228     }
1229   fputs (suffix, file);
1230 }
1231
1232 #include "gt-bitmap.h"