gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "flags.h"
  27 #include "obstack.h"
  28 #include "ggc.h"
  29 #include "bitmap.h"
  30
  31 /* Obstack to allocate bitmap elements from.  */
  32 static struct obstack bitmap_obstack;
  33 static int bitmap_obstack_init = FALSE;
  34 \f
  35 #ifndef INLINE
  36 #ifndef __GNUC__
  37 #define INLINE
  38 #else
  39 #define INLINE __inline__
  40 #endif
  41 #endif
  42
  43 /* Global data */
  44 bitmap_element bitmap_zero_bits;        /* An element of all zero bits.  */
  45 static bitmap_element *bitmap_free;     /* Freelist of bitmap elements.  */
  46 static GTY((deletable (""))) bitmap_element *bitmap_ggc_free;
  47
  48 static void bitmap_elem_to_freelist     PARAMS ((bitmap, bitmap_element *));
  49 static void bitmap_element_free         PARAMS ((bitmap, bitmap_element *));
  50 static bitmap_element *bitmap_element_allocate PARAMS ((bitmap));
  51 static int bitmap_element_zerop         PARAMS ((bitmap_element *));
  52 static void bitmap_element_link         PARAMS ((bitmap, bitmap_element *));
  53 static bitmap_element *bitmap_find_bit  PARAMS ((bitmap, unsigned int));
  54 \f
  55 /* Add ELEM to the appropriate freelist.  */
  56 static INLINE void
  57 bitmap_elem_to_freelist (head, elt)
  58      bitmap head;
  59      bitmap_element *elt;
  60 {
  61   if (head->using_obstack)
  62     {
  63       elt->next = bitmap_free;
  64       bitmap_free = elt;
  65     }
  66   else
  67     {
  68       elt->next = bitmap_ggc_free;
  69       bitmap_ggc_free = elt;
  70     }
  71 }
  72
  73 /* Free a bitmap element.  Since these are allocated off the
  74    bitmap_obstack, "free" actually means "put onto the freelist".  */
  75
  76 static INLINE void
  77 bitmap_element_free (head, elt)
  78      bitmap head;
  79      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 (head)
 108      bitmap head;
 109 {
 110   bitmap_element *element;
 111
 112   if (head->using_obstack)
 113     {
 114       if (bitmap_free != 0)
 115         {
 116           element = bitmap_free;
 117           bitmap_free = element->next;
 118         }
 119       else
 120         {
 121           /* We can't use gcc_obstack_init to initialize the obstack since
 122              print-rtl.c now calls bitmap functions, and bitmap is linked
 123              into the gen* functions.  */
 124           if (!bitmap_obstack_init)
 125             {
 126               bitmap_obstack_init = TRUE;
 127
 128               /* Let particular systems override the size of a chunk.  */
 129 #ifndef OBSTACK_CHUNK_SIZE
 130 #define OBSTACK_CHUNK_SIZE 0
 131 #endif
 132               /* Let them override the alloc and free routines too.  */
 133 #ifndef OBSTACK_CHUNK_ALLOC
 134 #define OBSTACK_CHUNK_ALLOC xmalloc
 135 #endif
 136 #ifndef OBSTACK_CHUNK_FREE
 137 #define OBSTACK_CHUNK_FREE free
 138 #endif
 139
 140 #if !defined(__GNUC__) || (__GNUC__ < 2)
 141 #define __alignof__(type) 0
 142 #endif
 143
 144               obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE,
 145                                           __alignof__ (bitmap_element),
 146                                           (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
 147                                           (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
 148             }
 149
 150           element = (bitmap_element *) obstack_alloc (&bitmap_obstack,
 151                                                       sizeof (bitmap_element));
 152         }
 153     }
 154   else
 155     {
 156       if (bitmap_ggc_free != NULL)
 157         {
 158           element = bitmap_ggc_free;
 159           bitmap_ggc_free = element->next;
 160         }
 161       else
 162         element = ggc_alloc (sizeof (bitmap_element));
 163     }
 164
 165   memset (element->bits, 0, sizeof (element->bits));
 166
 167   return element;
 168 }
 169
 170 /* Release any memory allocated by bitmaps.  */
 171
 172 void
 173 bitmap_release_memory ()
 174 {
 175   bitmap_free = 0;
 176   if (bitmap_obstack_init)
 177     {
 178       bitmap_obstack_init = FALSE;
 179       obstack_free (&bitmap_obstack, NULL);
 180     }
 181 }
 182
 183 /* Return nonzero if all bits in an element are zero.  */
 184
 185 static INLINE int
 186 bitmap_element_zerop (element)
 187      bitmap_element *element;
 188 {
 189 #if BITMAP_ELEMENT_WORDS == 2
 190   return (element->bits[0] | element->bits[1]) == 0;
 191 #else
 192   int i;
 193
 194   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 195     if (element->bits[i] != 0)
 196       return 0;
 197
 198   return 1;
 199 #endif
 200 }
 201 \f
 202 /* Link the bitmap element into the current bitmap linked list.  */
 203
 204 static INLINE void
 205 bitmap_element_link (head, element)
 206      bitmap head;
 207      bitmap_element *element;
 208 {
 209   unsigned int indx = element->indx;
 210   bitmap_element *ptr;
 211
 212   /* If this is the first and only element, set it in.  */
 213   if (head->first == 0)
 214     {
 215       element->next = element->prev = 0;
 216       head->first = element;
 217     }
 218
 219   /* If this index is less than that of the current element, it goes someplace
 220      before the current element.  */
 221   else if (indx < head->indx)
 222     {
 223       for (ptr = head->current;
 224            ptr->prev != 0 && ptr->prev->indx > indx;
 225            ptr = ptr->prev)
 226         ;
 227
 228       if (ptr->prev)
 229         ptr->prev->next = element;
 230       else
 231         head->first = element;
 232
 233       element->prev = ptr->prev;
 234       element->next = ptr;
 235       ptr->prev = element;
 236     }
 237
 238   /* Otherwise, it must go someplace after the current element.  */
 239   else
 240     {
 241       for (ptr = head->current;
 242            ptr->next != 0 && ptr->next->indx < indx;
 243            ptr = ptr->next)
 244         ;
 245
 246       if (ptr->next)
 247         ptr->next->prev = element;
 248
 249       element->next = ptr->next;
 250       element->prev = ptr;
 251       ptr->next = element;
 252     }
 253
 254   /* Set up so this is the first element searched.  */
 255   head->current = element;
 256   head->indx = indx;
 257 }
 258 \f
 259 /* Clear a bitmap by freeing the linked list.  */
 260
 261 INLINE void
 262 bitmap_clear (head)
 263      bitmap head;
 264 {
 265   bitmap_element *element, *next;
 266
 267   for (element = head->first; element != 0; element = next)
 268     {
 269       next = element->next;
 270       bitmap_elem_to_freelist (head, element);
 271     }
 272
 273   head->first = head->current = 0;
 274 }
 275 \f
 276 /* Copy a bitmap to another bitmap.  */
 277
 278 void
 279 bitmap_copy (to, from)
 280      bitmap to;
 281      bitmap from;
 282 {
 283   bitmap_element *from_ptr, *to_ptr = 0;
 284 #if BITMAP_ELEMENT_WORDS != 2
 285   int i;
 286 #endif
 287
 288   bitmap_clear (to);
 289
 290   /* Copy elements in forward direction one at a time */
 291   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 292     {
 293       bitmap_element *to_elt = bitmap_element_allocate (to);
 294
 295       to_elt->indx = from_ptr->indx;
 296
 297 #if BITMAP_ELEMENT_WORDS == 2
 298       to_elt->bits[0] = from_ptr->bits[0];
 299       to_elt->bits[1] = from_ptr->bits[1];
 300 #else
 301       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 302         to_elt->bits[i] = from_ptr->bits[i];
 303 #endif
 304
 305       /* Here we have a special case of bitmap_element_link, for the case
 306          where we know the links are being entered in sequence.  */
 307       if (to_ptr == 0)
 308         {
 309           to->first = to->current = to_elt;
 310           to->indx = from_ptr->indx;
 311           to_elt->next = to_elt->prev = 0;
 312         }
 313       else
 314         {
 315           to_elt->prev = to_ptr;
 316           to_elt->next = 0;
 317           to_ptr->next = to_elt;
 318         }
 319
 320       to_ptr = to_elt;
 321     }
 322 }
 323 \f
 324 /* Find a bitmap element that would hold a bitmap's bit.
 325    Update the `current' field even if we can't find an element that
 326    would hold the bitmap's bit to make eventual allocation
 327    faster.  */
 328
 329 static INLINE bitmap_element *
 330 bitmap_find_bit (head, bit)
 331      bitmap head;
 332      unsigned int bit;
 333 {
 334   bitmap_element *element;
 335   unsigned HOST_WIDE_INT indx = bit / BITMAP_ELEMENT_ALL_BITS;
 336
 337   if (head->current == 0
 338       || head->indx == indx)
 339     return head->current;
 340
 341   if (head->indx > indx)
 342     for (element = head->current;
 343          element->prev != 0 && element->indx > indx;
 344          element = element->prev)
 345       ;
 346
 347   else
 348     for (element = head->current;
 349          element->next != 0 && element->indx < indx;
 350          element = element->next)
 351       ;
 352
 353   /* `element' is the nearest to the one we want.  If it's not the one we
 354      want, the one we want doesn't exist.  */
 355   head->current = element;
 356   head->indx = element->indx;
 357   if (element != 0 && element->indx != indx)
 358     element = 0;
 359
 360   return element;
 361 }
 362 \f
 363 /* Clear a single bit in a bitmap.  */
 364
 365 void
 366 bitmap_clear_bit (head, bit)
 367      bitmap head;
 368      int bit;
 369 {
 370   bitmap_element *ptr = bitmap_find_bit (head, bit);
 371
 372   if (ptr != 0)
 373     {
 374       unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 375       unsigned word_num = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT)
 376                            % BITMAP_ELEMENT_WORDS);
 377       ptr->bits[word_num] &= ~ (((unsigned HOST_WIDE_INT) 1) << bit_num);
 378
 379       /* If we cleared the entire word, free up the element */
 380       if (bitmap_element_zerop (ptr))
 381         bitmap_element_free (head, ptr);
 382     }
 383 }
 384
 385 /* Set a single bit in a bitmap.  */
 386
 387 void
 388 bitmap_set_bit (head, bit)
 389      bitmap head;
 390      int bit;
 391 {
 392   bitmap_element *ptr = bitmap_find_bit (head, bit);
 393   unsigned word_num
 394     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 395   unsigned bit_num  = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 396   unsigned HOST_WIDE_INT bit_val = ((unsigned HOST_WIDE_INT) 1) << bit_num;
 397
 398   if (ptr == 0)
 399     {
 400       ptr = bitmap_element_allocate (head);
 401       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 402       ptr->bits[word_num] = bit_val;
 403       bitmap_element_link (head, ptr);
 404     }
 405   else
 406     ptr->bits[word_num] |= bit_val;
 407 }
 408
 409 /* Return whether a bit is set within a bitmap.  */
 410
 411 int
 412 bitmap_bit_p (head, bit)
 413      bitmap head;
 414      int bit;
 415 {
 416   bitmap_element *ptr;
 417   unsigned bit_num;
 418   unsigned word_num;
 419
 420   ptr = bitmap_find_bit (head, bit);
 421   if (ptr == 0)
 422     return 0;
 423
 424   bit_num = bit % (unsigned) HOST_BITS_PER_WIDE_INT;
 425   word_num
 426     = ((bit / (unsigned) HOST_BITS_PER_WIDE_INT) % BITMAP_ELEMENT_WORDS);
 427
 428   return (ptr->bits[word_num] >> bit_num) & 1;
 429 }
 430 \f
 431 /* Return the bit number of the first set bit in the bitmap, or -1
 432    if the bitmap is empty.  */
 433
 434 int
 435 bitmap_first_set_bit (a)
 436      bitmap a;
 437 {
 438   bitmap_element *ptr = a->first;
 439   unsigned HOST_WIDE_INT word;
 440   unsigned word_num, bit_num;
 441
 442   if (ptr == NULL)
 443     return -1;
 444
 445 #if BITMAP_ELEMENT_WORDS == 2
 446   word_num = 0, word = ptr->bits[0];
 447   if (word == 0)
 448     word_num = 1, word = ptr->bits[1];
 449 #else
 450   for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
 451     if ((word = ptr->bits[word_num]) != 0)
 452       break;
 453 #endif
 454
 455   /* Binary search for the first set bit.  */
 456   /* ??? It'd be nice to know if ffs or ffsl was available.  */
 457
 458   bit_num = 0;
 459   word = word & -word;
 460
 461 #if HOST_BITS_PER_WIDE_INT > 64
 462  #error "Fill out the table."
 463 #endif
 464 #if HOST_BITS_PER_WIDE_INT > 32
 465   if ((word & 0xffffffff) == 0)
 466     word >>= 32, bit_num += 32;
 467 #endif
 468   if ((word & 0xffff) == 0)
 469     word >>= 16, bit_num += 16;
 470   if ((word & 0xff) == 0)
 471     word >>= 8, bit_num += 8;
 472   if (word & 0xf0)
 473     bit_num += 4;
 474   if (word & 0xcc)
 475     bit_num += 2;
 476   if (word & 0xaa)
 477     bit_num += 1;
 478
 479   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 480           + word_num * HOST_BITS_PER_WIDE_INT
 481           + bit_num);
 482 }
 483
 484 /* Return the bit number of the last set bit in the bitmap, or -1
 485    if the bitmap is empty.  */
 486
 487 int
 488 bitmap_last_set_bit (a)
 489      bitmap a;
 490 {
 491   bitmap_element *ptr = a->first;
 492   unsigned HOST_WIDE_INT word;
 493   unsigned word_num, bit_num;
 494
 495   if (ptr == NULL)
 496     return -1;
 497
 498   while (ptr->next != NULL)
 499     ptr = ptr->next;
 500
 501 #if BITMAP_ELEMENT_WORDS == 2
 502   word_num = 1, word = ptr->bits[1];
 503   if (word == 0)
 504     word_num = 0, word = ptr->bits[0];
 505 #else
 506   for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
 507     if ((word = ptr->bits[word_num]) != 0)
 508       break;
 509 #endif
 510
 511   /* Binary search for the last set bit.  */
 512
 513   bit_num = 0;
 514 #if HOST_BITS_PER_WIDE_INT > 64
 515  #error "Fill out the table."
 516 #endif
 517 #if HOST_BITS_PER_WIDE_INT > 32
 518   if (word & ~ (unsigned HOST_WIDE_INT) 0xffffffff)
 519     word >>= 32, bit_num += 32;
 520 #endif
 521   if (word & 0xffff0000)
 522     word >>= 16, bit_num += 16;
 523   if (word & 0xff00)
 524     word >>= 8, bit_num += 8;
 525   if (word & 0xf0)
 526     word >>= 4, bit_num += 4;
 527   if (word & 0xc)
 528     word >>= 2, bit_num += 2;
 529   if (word & 0x2)
 530     bit_num += 1;
 531
 532   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 533           + word_num * HOST_BITS_PER_WIDE_INT
 534           + bit_num);
 535 }
 536 \f
 537 /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
 538    a specific bit manipulation.  Return true if TO changes.  */
 539
 540 int
 541 bitmap_operation (to, from1, from2, operation)
 542      bitmap to;
 543      bitmap from1;
 544      bitmap from2;
 545      enum bitmap_bits operation;
 546 {
 547 #define HIGHEST_INDEX (unsigned int) ~0
 548
 549   bitmap_element *from1_ptr = from1->first;
 550   bitmap_element *from2_ptr = from2->first;
 551   unsigned int indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 552   unsigned int indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 553   bitmap_element *to_ptr = to->first;
 554   bitmap_element *from1_tmp;
 555   bitmap_element *from2_tmp;
 556   bitmap_element *to_tmp;
 557   unsigned int indx;
 558   int changed = 0;
 559
 560 #if BITMAP_ELEMENT_WORDS == 2
 561 #define DOIT(OP)                                        \
 562   do {                                                  \
 563     unsigned HOST_WIDE_INT t0, t1, f10, f11, f20, f21;  \
 564     f10 = from1_tmp->bits[0];                           \
 565     f20 = from2_tmp->bits[0];                           \
 566     t0 = f10 OP f20;                                    \
 567     changed |= (t0 != to_tmp->bits[0]);                 \
 568     f11 = from1_tmp->bits[1];                           \
 569     f21 = from2_tmp->bits[1];                           \
 570     t1 = f11 OP f21;                                    \
 571     changed |= (t1 != to_tmp->bits[1]);                 \
 572     to_tmp->bits[0] = t0;                               \
 573     to_tmp->bits[1] = t1;                               \
 574   } while (0)
 575 #else
 576 #define DOIT(OP)                                        \
 577   do {                                                  \
 578     unsigned HOST_WIDE_INT t, f1, f2;                   \
 579     int i;                                              \
 580     for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i)          \
 581       {                                                 \
 582         f1 = from1_tmp->bits[i];                        \
 583         f2 = from2_tmp->bits[i];                        \
 584         t = f1 OP f2;                                   \
 585         changed |= (t != to_tmp->bits[i]);              \
 586         to_tmp->bits[i] = t;                            \
 587       }                                                 \
 588   } while (0)
 589 #endif
 590
 591   to->first = to->current = 0;
 592
 593   while (from1_ptr != 0 || from2_ptr != 0)
 594     {
 595       /* Figure out whether we need to substitute zero elements for
 596          missing links.  */
 597       if (indx1 == indx2)
 598         {
 599           indx = indx1;
 600           from1_tmp = from1_ptr;
 601           from2_tmp = from2_ptr;
 602           from1_ptr = from1_ptr->next;
 603           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 604           from2_ptr = from2_ptr->next;
 605           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 606         }
 607       else if (indx1 < indx2)
 608         {
 609           indx = indx1;
 610           from1_tmp = from1_ptr;
 611           from2_tmp = &bitmap_zero_bits;
 612           from1_ptr = from1_ptr->next;
 613           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 614         }
 615       else
 616         {
 617           indx = indx2;
 618           from1_tmp = &bitmap_zero_bits;
 619           from2_tmp = from2_ptr;
 620           from2_ptr = from2_ptr->next;
 621           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 622         }
 623
 624       /* Find the appropriate element from TO.  Begin by discarding
 625          elements that we've skipped.  */
 626       while (to_ptr && to_ptr->indx < indx)
 627         {
 628           changed = 1;
 629           to_tmp = to_ptr;
 630           to_ptr = to_ptr->next;
 631           bitmap_elem_to_freelist (to, to_tmp);
 632         }
 633       if (to_ptr && to_ptr->indx == indx)
 634         {
 635           to_tmp = to_ptr;
 636           to_ptr = to_ptr->next;
 637         }
 638       else
 639         to_tmp = bitmap_element_allocate (to);
 640
 641       /* Do the operation, and if any bits are set, link it into the
 642          linked list.  */
 643       switch (operation)
 644         {
 645         default:
 646           abort ();
 647
 648         case BITMAP_AND:
 649           DOIT (&);
 650           break;
 651
 652         case BITMAP_AND_COMPL:
 653           DOIT (&~);
 654           break;
 655
 656         case BITMAP_IOR:
 657           DOIT (|);
 658           break;
 659         case BITMAP_IOR_COMPL:
 660           DOIT (|~);
 661           break;
 662         case BITMAP_XOR:
 663           DOIT (^);
 664           break;
 665         }
 666
 667       if (! bitmap_element_zerop (to_tmp))
 668         {
 669           to_tmp->indx = indx;
 670           bitmap_element_link (to, to_tmp);
 671         }
 672       else
 673         {
 674           bitmap_elem_to_freelist (to, to_tmp);
 675         }
 676     }
 677
 678   /* If we have elements of TO left over, free the lot.  */
 679   if (to_ptr)
 680     {
 681       changed = 1;
 682       for (to_tmp = to_ptr; to_tmp->next ; to_tmp = to_tmp->next)
 683         continue;
 684       if (to->using_obstack)
 685         {
 686           to_tmp->next = bitmap_free;
 687           bitmap_free = to_ptr;
 688         }
 689       else
 690         {
 691           to_tmp->next = bitmap_ggc_free;
 692           bitmap_ggc_free = to_ptr;
 693         }
 694     }
 695
 696 #undef DOIT
 697
 698   return changed;
 699 }
 700
 701 /* Return true if two bitmaps are identical.  */
 702
 703 int
 704 bitmap_equal_p (a, b)
 705      bitmap a;
 706      bitmap b;
 707 {
 708   bitmap_head c;
 709   int ret;
 710
 711   memset (&c, 0, sizeof (c));
 712   ret = ! bitmap_operation (&c, a, b, BITMAP_XOR);
 713   bitmap_clear (&c);
 714
 715   return ret;
 716 }
 717 \f
 718 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
 719    bitmap FROM2.  */
 720
 721 void
 722 bitmap_ior_and_compl (to, from1, from2)
 723      bitmap to;
 724      bitmap from1;
 725      bitmap from2;
 726 {
 727   bitmap_head tmp;
 728
 729   tmp.first = tmp.current = 0;
 730   tmp.using_obstack = 0;
 731
 732   bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
 733   bitmap_operation (to, to, &tmp, BITMAP_IOR);
 734   bitmap_clear (&tmp);
 735 }
 736
 737 int
 738 bitmap_union_of_diff (dst, a, b, c)
 739      bitmap dst;
 740      bitmap a;
 741      bitmap b;
 742      bitmap c;
 743 {
 744   bitmap_head tmp;
 745   int changed;
 746
 747   tmp.first = tmp.current = 0;
 748   tmp.using_obstack = 0;
 749
 750   bitmap_operation (&tmp, b, c, BITMAP_AND_COMPL);
 751   changed = bitmap_operation (dst, &tmp, a, BITMAP_IOR);
 752   bitmap_clear (&tmp);
 753
 754   return changed;
 755 }
 756 \f
 757 /* Initialize a bitmap header.  */
 758
 759 bitmap
 760 bitmap_initialize (head, using_obstack)
 761      bitmap head;
 762      int using_obstack;
 763 {
 764   if (head == NULL && ! using_obstack)
 765     head = ggc_alloc (sizeof (*head));
 766
 767   head->first = head->current = 0;
 768   head->using_obstack = using_obstack;
 769
 770   return head;
 771 }
 772 \f
 773 /* Debugging function to print out the contents of a bitmap.  */
 774
 775 void
 776 debug_bitmap_file (file, head)
 777      FILE *file;
 778      bitmap head;
 779 {
 780   bitmap_element *ptr;
 781
 782   fprintf (file, "\nfirst = ");
 783   fprintf (file, HOST_PTR_PRINTF, (PTR) head->first);
 784   fprintf (file, " current = ");
 785   fprintf (file, HOST_PTR_PRINTF, (PTR) head->current);
 786   fprintf (file, " indx = %u\n", head->indx);
 787
 788   for (ptr = head->first; ptr; ptr = ptr->next)
 789     {
 790       int i, j, col = 26;
 791
 792       fprintf (file, "\t");
 793       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
 794       fprintf (file, " next = ");
 795       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->next);
 796       fprintf (file, " prev = ");
 797       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->prev);
 798       fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
 799
 800       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 801         for (j = 0; j < HOST_BITS_PER_WIDE_INT; j++)
 802           if ((ptr->bits[i] >> j) & 1)
 803             {
 804               if (col > 70)
 805                 {
 806                   fprintf (file, "\n\t\t\t");
 807                   col = 24;
 808                 }
 809
 810               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 811                                      + i * HOST_BITS_PER_WIDE_INT + j));
 812               col += 4;
 813             }
 814
 815       fprintf (file, " }\n");
 816     }
 817 }
 818
 819 /* Function to be called from the debugger to print the contents
 820    of a bitmap.  */
 821
 822 void
 823 debug_bitmap (head)
 824      bitmap head;
 825 {
 826   debug_bitmap_file (stdout, head);
 827 }
 828
 829 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
 830    it does not print anything but the bits.  */
 831
 832 void
 833 bitmap_print (file, head, prefix, suffix)
 834      FILE *file;
 835      bitmap head;
 836      const char *prefix;
 837      const char *suffix;
 838 {
 839   const char *comma = "";
 840   int i;
 841
 842   fputs (prefix, file);
 843   EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
 844                             {
 845                               fprintf (file, "%s%d", comma, i);
 846                               comma = ", ";
 847                             });
 848   fputs (suffix, file);
 849 }
 850
 851 #include "gt-bitmap.h"