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