gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
   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, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "obstack.h"
  29 #include "ggc.h"
  30 #include "bitmap.h"
  31
  32 /* Global data */
  33 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
  34 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
  35 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
  36                                                             GC'd elements.  */
  37
  38 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
  39 static void bitmap_element_free (bitmap, bitmap_element *);
  40 static bitmap_element *bitmap_element_allocate (bitmap);
  41 static int bitmap_element_zerop (bitmap_element *);
  42 static void bitmap_element_link (bitmap, bitmap_element *);
  43 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
  44 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
  45 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
  46 \f
  47
  48 /* Add ELEM to the appropriate freelist.  */
  49 static inline void
  50 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
  51 {
  52   bitmap_obstack *bit_obstack = head->obstack;
  53
  54   elt->next = NULL;
  55   if (bit_obstack)
  56     {
  57       elt->prev = bit_obstack->elements;
  58       bit_obstack->elements = elt;
  59     }
  60   else
  61     {
  62       elt->prev = bitmap_ggc_free;
  63       bitmap_ggc_free = elt;
  64     }
  65 }
  66
  67 /* Free a bitmap element.  Since these are allocated off the
  68    bitmap_obstack, "free" actually means "put onto the freelist".  */
  69
  70 static inline void
  71 bitmap_element_free (bitmap head, bitmap_element *elt)
  72 {
  73   bitmap_element *next = elt->next;
  74   bitmap_element *prev = elt->prev;
  75
  76   if (prev)
  77     prev->next = next;
  78
  79   if (next)
  80     next->prev = prev;
  81
  82   if (head->first == elt)
  83     head->first = next;
  84
  85   /* Since the first thing we try is to insert before current,
  86      make current the next entry in preference to the previous.  */
  87   if (head->current == elt)
  88     {
  89       head->current = next != 0 ? next : prev;
  90       if (head->current)
  91         head->indx = head->current->indx;
  92       else
  93         head->indx = 0;
  94     }
  95   bitmap_elem_to_freelist (head, elt);
  96 }
  97 \f
  98 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
  99
 100 static inline bitmap_element *
 101 bitmap_element_allocate (bitmap head)
 102 {
 103   bitmap_element *element;
 104   bitmap_obstack *bit_obstack = head->obstack;
 105
 106   if (bit_obstack)
 107     {
 108       element = bit_obstack->elements;
 109
 110       if (element)
 111         /* Use up the inner list first before looking at the next
 112            element of the outer list.  */
 113         if (element->next)
 114           {
 115             bit_obstack->elements = element->next;
 116             bit_obstack->elements->prev = element->prev;
 117           }
 118         else
 119           /*  Inner list was just a singleton.  */
 120           bit_obstack->elements = element->prev;
 121       else
 122         element = XOBNEW (&bit_obstack->obstack, bitmap_element);
 123     }
 124   else
 125     {
 126       element = bitmap_ggc_free;
 127       if (element)
 128         /* Use up the inner list first before looking at the next
 129            element of the outer list.  */
 130         if (element->next)
 131           {
 132             bitmap_ggc_free = element->next;
 133             bitmap_ggc_free->prev = element->prev;
 134           }
 135         else
 136           /*  Inner list was just a singleton.  */
 137           bitmap_ggc_free = element->prev;
 138       else
 139         element = GGC_NEW (bitmap_element);
 140     }
 141
 142   memset (element->bits, 0, sizeof (element->bits));
 143
 144   return element;
 145 }
 146
 147 /* Remove ELT and all following elements from bitmap HEAD.  */
 148
 149 void
 150 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 151 {
 152   bitmap_element *prev;
 153   bitmap_obstack *bit_obstack = head->obstack;
 154
 155   if (!elt) return;
 156
 157   prev = elt->prev;
 158   if (prev)
 159     {
 160       prev->next = NULL;
 161       if (head->current->indx > prev->indx)
 162         {
 163           head->current = prev;
 164           head->indx = prev->indx;
 165         }
 166     }
 167   else
 168     {
 169       head->first = NULL;
 170       head->current = NULL;
 171       head->indx = 0;
 172     }
 173
 174   /* Put the entire list onto the free list in one operation. */
 175   if (bit_obstack)
 176     {
 177       elt->prev = bit_obstack->elements;
 178       bit_obstack->elements = elt;
 179     }
 180   else
 181     {
 182       elt->prev = bitmap_ggc_free;
 183       bitmap_ggc_free = elt;
 184     }
 185 }
 186
 187 /* Clear a bitmap by freeing the linked list.  */
 188
 189 inline void
 190 bitmap_clear (bitmap head)
 191 {
 192   if (head->first)
 193     bitmap_elt_clear_from (head, head->first);
 194 }
 195 \f
 196 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
 197    the default bitmap obstack.  */
 198
 199 void
 200 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
 201 {
 202   if (!bit_obstack)
 203     bit_obstack = &bitmap_default_obstack;
 204
 205 #if !defined(__GNUC__) || (__GNUC__ < 2)
 206 #define __alignof__(type) 0
 207 #endif
 208
 209   bit_obstack->elements = NULL;
 210   bit_obstack->heads = NULL;
 211   obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
 212                               __alignof__ (bitmap_element),
 213                               obstack_chunk_alloc,
 214                               obstack_chunk_free);
 215 }
 216
 217 /* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
 218    release the default bitmap obstack.  */
 219
 220 void
 221 bitmap_obstack_release (bitmap_obstack *bit_obstack)
 222 {
 223   if (!bit_obstack)
 224     bit_obstack = &bitmap_default_obstack;
 225
 226   bit_obstack->elements = NULL;
 227   bit_obstack->heads = NULL;
 228   obstack_free (&bit_obstack->obstack, NULL);
 229 }
 230
 231 /* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
 232    it on the default bitmap obstack.  */
 233
 234 bitmap
 235 bitmap_obstack_alloc (bitmap_obstack *bit_obstack)
 236 {
 237   bitmap map;
 238
 239   if (!bit_obstack)
 240     bit_obstack = &bitmap_default_obstack;
 241   map = bit_obstack->heads;
 242   if (map)
 243     bit_obstack->heads = (void *)map->first;
 244   else
 245     map = XOBNEW (&bit_obstack->obstack, bitmap_head);
 246   bitmap_initialize (map, bit_obstack);
 247
 248   return map;
 249 }
 250
 251 /* Create a new GCd bitmap.  */
 252
 253 bitmap
 254 bitmap_gc_alloc (void)
 255 {
 256   bitmap map;
 257
 258   map = GGC_NEW (struct bitmap_head_def);
 259   bitmap_initialize (map, NULL);
 260
 261   return map;
 262 }
 263
 264 /* Release an obstack allocated bitmap.  */
 265
 266 void
 267 bitmap_obstack_free (bitmap map)
 268 {
 269   if (map)
 270     {
 271       bitmap_clear (map);
 272       map->first = (void *)map->obstack->heads;
 273       map->obstack->heads = map;
 274     }
 275 }
 276
 277 \f
 278 /* Return nonzero if all bits in an element are zero.  */
 279
 280 static inline int
 281 bitmap_element_zerop (bitmap_element *element)
 282 {
 283 #if BITMAP_ELEMENT_WORDS == 2
 284   return (element->bits[0] | element->bits[1]) == 0;
 285 #else
 286   unsigned i;
 287
 288   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 289     if (element->bits[i] != 0)
 290       return 0;
 291
 292   return 1;
 293 #endif
 294 }
 295 \f
 296 /* Link the bitmap element into the current bitmap linked list.  */
 297
 298 static inline void
 299 bitmap_element_link (bitmap head, bitmap_element *element)
 300 {
 301   unsigned int indx = element->indx;
 302   bitmap_element *ptr;
 303
 304   /* If this is the first and only element, set it in.  */
 305   if (head->first == 0)
 306     {
 307       element->next = element->prev = 0;
 308       head->first = element;
 309     }
 310
 311   /* If this index is less than that of the current element, it goes someplace
 312      before the current element.  */
 313   else if (indx < head->indx)
 314     {
 315       for (ptr = head->current;
 316            ptr->prev != 0 && ptr->prev->indx > indx;
 317            ptr = ptr->prev)
 318         ;
 319
 320       if (ptr->prev)
 321         ptr->prev->next = element;
 322       else
 323         head->first = element;
 324
 325       element->prev = ptr->prev;
 326       element->next = ptr;
 327       ptr->prev = element;
 328     }
 329
 330   /* Otherwise, it must go someplace after the current element.  */
 331   else
 332     {
 333       for (ptr = head->current;
 334            ptr->next != 0 && ptr->next->indx < indx;
 335            ptr = ptr->next)
 336         ;
 337
 338       if (ptr->next)
 339         ptr->next->prev = element;
 340
 341       element->next = ptr->next;
 342       element->prev = ptr;
 343       ptr->next = element;
 344     }
 345
 346   /* Set up so this is the first element searched.  */
 347   head->current = element;
 348   head->indx = indx;
 349 }
 350
 351 /* Insert a new uninitialized element into bitmap HEAD after element
 352    ELT.  If ELT is NULL, insert the element at the start.  Return the
 353    new element.  */
 354
 355 static bitmap_element *
 356 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
 357 {
 358   bitmap_element *node = bitmap_element_allocate (head);
 359   node->indx = indx;
 360
 361   if (!elt)
 362     {
 363       if (!head->current)
 364         {
 365           head->current = node;
 366           head->indx = indx;
 367         }
 368       node->next = head->first;
 369       if (node->next)
 370         node->next->prev = node;
 371       head->first = node;
 372       node->prev = NULL;
 373     }
 374   else
 375     {
 376       gcc_assert (head->current);
 377       node->next = elt->next;
 378       if (node->next)
 379         node->next->prev = node;
 380       elt->next = node;
 381       node->prev = elt;
 382     }
 383   return node;
 384 }
 385 \f
 386 /* Copy a bitmap to another bitmap.  */
 387
 388 void
 389 bitmap_copy (bitmap to, bitmap from)
 390 {
 391   bitmap_element *from_ptr, *to_ptr = 0;
 392
 393   bitmap_clear (to);
 394
 395   /* Copy elements in forward direction one at a time.  */
 396   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 397     {
 398       bitmap_element *to_elt = bitmap_element_allocate (to);
 399
 400       to_elt->indx = from_ptr->indx;
 401       memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
 402
 403       /* Here we have a special case of bitmap_element_link, for the case
 404          where we know the links are being entered in sequence.  */
 405       if (to_ptr == 0)
 406         {
 407           to->first = to->current = to_elt;
 408           to->indx = from_ptr->indx;
 409           to_elt->next = to_elt->prev = 0;
 410         }
 411       else
 412         {
 413           to_elt->prev = to_ptr;
 414           to_elt->next = 0;
 415           to_ptr->next = to_elt;
 416         }
 417
 418       to_ptr = to_elt;
 419     }
 420 }
 421 \f
 422 /* Find a bitmap element that would hold a bitmap's bit.
 423    Update the `current' field even if we can't find an element that
 424    would hold the bitmap's bit to make eventual allocation
 425    faster.  */
 426
 427 static inline bitmap_element *
 428 bitmap_find_bit (bitmap head, unsigned int bit)
 429 {
 430   bitmap_element *element;
 431   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 432
 433   if (head->current == 0
 434       || head->indx == indx)
 435     return head->current;
 436
 437   if (head->indx < indx)
 438     /* INDX is beyond head->indx.  Search from head->current
 439        forward.  */
 440     for (element = head->current;
 441          element->next != 0 && element->indx < indx;
 442          element = element->next)
 443       ;
 444
 445   else if (head->indx / 2 < indx)
 446     /* INDX is less than head->indx and closer to head->indx than to
 447        0.  Search from head->current backward.  */
 448     for (element = head->current;
 449          element->prev != 0 && element->indx > indx;
 450          element = element->prev)
 451       ;
 452
 453   else
 454     /* INDX is less than head->indx and closer to 0 than to
 455        head->indx.  Search from head->first forward.  */
 456     for (element = head->first;
 457          element->next != 0 && element->indx < indx;
 458          element = element->next)
 459       ;
 460
 461   /* `element' is the nearest to the one we want.  If it's not the one we
 462      want, the one we want doesn't exist.  */
 463   head->current = element;
 464   head->indx = element->indx;
 465   if (element != 0 && element->indx != indx)
 466     element = 0;
 467
 468   return element;
 469 }
 470 \f
 471 /* Clear a single bit in a bitmap.  */
 472
 473 void
 474 bitmap_clear_bit (bitmap head, int bit)
 475 {
 476   bitmap_element *ptr = bitmap_find_bit (head, bit);
 477
 478   if (ptr != 0)
 479     {
 480       unsigned bit_num  = bit % BITMAP_WORD_BITS;
 481       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 482       ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
 483
 484       /* If we cleared the entire word, free up the element.  */
 485       if (bitmap_element_zerop (ptr))
 486         bitmap_element_free (head, ptr);
 487     }
 488 }
 489
 490 /* Set a single bit in a bitmap.  */
 491
 492 void
 493 bitmap_set_bit (bitmap head, int bit)
 494 {
 495   bitmap_element *ptr = bitmap_find_bit (head, bit);
 496   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 497   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 498   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 499
 500   if (ptr == 0)
 501     {
 502       ptr = bitmap_element_allocate (head);
 503       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 504       ptr->bits[word_num] = bit_val;
 505       bitmap_element_link (head, ptr);
 506     }
 507   else
 508     ptr->bits[word_num] |= bit_val;
 509 }
 510
 511 /* Return whether a bit is set within a bitmap.  */
 512
 513 int
 514 bitmap_bit_p (bitmap head, int bit)
 515 {
 516   bitmap_element *ptr;
 517   unsigned bit_num;
 518   unsigned word_num;
 519
 520   ptr = bitmap_find_bit (head, bit);
 521   if (ptr == 0)
 522     return 0;
 523
 524   bit_num = bit % BITMAP_WORD_BITS;
 525   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 526
 527   return (ptr->bits[word_num] >> bit_num) & 1;
 528 }
 529 \f
 530 #if GCC_VERSION < 3400
 531 /* Table of number of set bits in a character, indexed by value of char.  */
 532 static unsigned char popcount_table[] =
 533 {
 534     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 535     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 536     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 537     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 538     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 539     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 540     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 541     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
 542 };
 543
 544 static unsigned long
 545 bitmap_popcount (BITMAP_WORD a)
 546 {
 547   unsigned long ret = 0;
 548   unsigned i;
 549
 550   /* Just do this the table way for now  */
 551   for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
 552     ret += popcount_table[(a >> i) & 0xff];
 553   return ret;
 554 }
 555 #endif
 556 /* Count the number of bits set in the bitmap, and return it.  */
 557
 558 unsigned long
 559 bitmap_count_bits (bitmap a)
 560 {
 561   unsigned long count = 0;
 562   bitmap_element *elt;
 563   unsigned ix;
 564
 565   for (elt = a->first; elt; elt = elt->next)
 566     {
 567       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 568         {
 569 #if GCC_VERSION >= 3400
 570           /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 571          of BITMAP_WORD is not material.  */
 572           count += __builtin_popcountl (elt->bits[ix]);
 573 #else
 574           count += bitmap_popcount (elt->bits[ix]);
 575 #endif
 576         }
 577     }
 578   return count;
 579 }
 580
 581
 582
 583 /* Return the bit number of the first set bit in the bitmap.  The
 584    bitmap must be non-empty.  */
 585
 586 unsigned
 587 bitmap_first_set_bit (bitmap a)
 588 {
 589   bitmap_element *elt = a->first;
 590   unsigned bit_no;
 591   BITMAP_WORD word;
 592   unsigned ix;
 593
 594   gcc_assert (elt);
 595   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 596   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 597     {
 598       word = elt->bits[ix];
 599       if (word)
 600         goto found_bit;
 601     }
 602   gcc_unreachable ();
 603  found_bit:
 604   bit_no += ix * BITMAP_WORD_BITS;
 605
 606 #if GCC_VERSION >= 3004
 607   gcc_assert (sizeof(long) == sizeof (word));
 608   bit_no += __builtin_ctzl (word);
 609 #else
 610   /* Binary search for the first set bit.  */
 611 #if BITMAP_WORD_BITS > 64
 612 #error "Fill out the table."
 613 #endif
 614 #if BITMAP_WORD_BITS > 32
 615   if (!(word & 0xffffffff))
 616     word >>= 32, bit_no += 32;
 617 #endif
 618   if (!(word & 0xffff))
 619     word >>= 16, bit_no += 16;
 620   if (!(word & 0xff))
 621     word >>= 8, bit_no += 8;
 622   if (!(word & 0xf))
 623     word >>= 4, bit_no += 4;
 624   if (!(word & 0x3))
 625     word >>= 2, bit_no += 2;
 626   if (!(word & 0x1))
 627     word >>= 1, bit_no += 1;
 628
 629  gcc_assert (word & 1);
 630 #endif
 631  return bit_no;
 632 }
 633 \f
 634
 635 /* DST = A & B.  */
 636
 637 void
 638 bitmap_and (bitmap dst, bitmap a, bitmap b)
 639 {
 640   bitmap_element *dst_elt = dst->first;
 641   bitmap_element *a_elt = a->first;
 642   bitmap_element *b_elt = b->first;
 643   bitmap_element *dst_prev = NULL;
 644
 645   gcc_assert (dst != a && dst != b);
 646
 647   if (a == b)
 648     {
 649       bitmap_copy (dst, a);
 650       return;
 651     }
 652
 653   while (a_elt && b_elt)
 654     {
 655       if (a_elt->indx < b_elt->indx)
 656         a_elt = a_elt->next;
 657       else if (b_elt->indx < a_elt->indx)
 658         b_elt = b_elt->next;
 659       else
 660         {
 661           /* Matching elts, generate A & B.  */
 662           unsigned ix;
 663           BITMAP_WORD ior = 0;
 664
 665           if (!dst_elt)
 666             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 667           else
 668             dst_elt->indx = a_elt->indx;
 669           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 670             {
 671               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 672
 673               dst_elt->bits[ix] = r;
 674               ior |= r;
 675             }
 676           if (ior)
 677             {
 678               dst_prev = dst_elt;
 679               dst_elt = dst_elt->next;
 680             }
 681           a_elt = a_elt->next;
 682           b_elt = b_elt->next;
 683         }
 684     }
 685   bitmap_elt_clear_from (dst, dst_elt);
 686   gcc_assert (!dst->current == !dst->first);
 687   if (dst->current)
 688     dst->indx = dst->current->indx;
 689 }
 690
 691 /* A &= B.  */
 692
 693 void
 694 bitmap_and_into (bitmap a, bitmap b)
 695 {
 696   bitmap_element *a_elt = a->first;
 697   bitmap_element *b_elt = b->first;
 698   bitmap_element *next;
 699
 700   if (a == b)
 701     return;
 702
 703   while (a_elt && b_elt)
 704     {
 705       if (a_elt->indx < b_elt->indx)
 706         {
 707           next = a_elt->next;
 708           bitmap_element_free (a, a_elt);
 709           a_elt = next;
 710         }
 711       else if (b_elt->indx < a_elt->indx)
 712         b_elt = b_elt->next;
 713       else
 714         {
 715           /* Matching elts, generate A &= B.  */
 716           unsigned ix;
 717           BITMAP_WORD ior = 0;
 718
 719           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 720             {
 721               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 722
 723               a_elt->bits[ix] = r;
 724               ior |= r;
 725             }
 726           next = a_elt->next;
 727           if (!ior)
 728             bitmap_element_free (a, a_elt);
 729           a_elt = next;
 730           b_elt = b_elt->next;
 731         }
 732     }
 733   bitmap_elt_clear_from (a, a_elt);
 734   gcc_assert (!a->current == !a->first);
 735   gcc_assert (!a->current || a->indx == a->current->indx);
 736 }
 737
 738 /* DST = A & ~B  */
 739
 740 void
 741 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 742 {
 743   bitmap_element *dst_elt = dst->first;
 744   bitmap_element *a_elt = a->first;
 745   bitmap_element *b_elt = b->first;
 746   bitmap_element *dst_prev = NULL;
 747
 748   gcc_assert (dst != a && dst != b);
 749
 750   if (a == b)
 751     {
 752       bitmap_clear (dst);
 753       return;
 754     }
 755
 756   while (a_elt)
 757     {
 758       if (!b_elt || a_elt->indx < b_elt->indx)
 759         {
 760           /* Copy a_elt.  */
 761           if (!dst_elt)
 762             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 763           else
 764             dst_elt->indx = a_elt->indx;
 765           memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 766           dst_prev = dst_elt;
 767           dst_elt = dst_elt->next;
 768           a_elt = a_elt->next;
 769         }
 770       else if (b_elt->indx < a_elt->indx)
 771         b_elt = b_elt->next;
 772       else
 773         {
 774           /* Matching elts, generate A & ~B.  */
 775           unsigned ix;
 776           BITMAP_WORD ior = 0;
 777
 778           if (!dst_elt)
 779             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 780           else
 781             dst_elt->indx = a_elt->indx;
 782           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 783             {
 784               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 785
 786               dst_elt->bits[ix] = r;
 787               ior |= r;
 788             }
 789           if (ior)
 790             {
 791               dst_prev = dst_elt;
 792               dst_elt = dst_elt->next;
 793             }
 794           a_elt = a_elt->next;
 795           b_elt = b_elt->next;
 796         }
 797     }
 798   bitmap_elt_clear_from (dst, dst_elt);
 799   gcc_assert (!dst->current == !dst->first);
 800   if (dst->current)
 801     dst->indx = dst->current->indx;
 802 }
 803
 804 /* A &= ~B. Returns true if A changes */
 805
 806 bool
 807 bitmap_and_compl_into (bitmap a, bitmap b)
 808 {
 809   bitmap_element *a_elt = a->first;
 810   bitmap_element *b_elt = b->first;
 811   bitmap_element *next;
 812   BITMAP_WORD changed = 0;
 813
 814   if (a == b)
 815     {
 816       if (bitmap_empty_p (a))
 817         return false;
 818       else
 819         {
 820           bitmap_clear (a);
 821           return true;
 822         }
 823     }
 824
 825   while (a_elt && b_elt)
 826     {
 827       if (a_elt->indx < b_elt->indx)
 828         a_elt = a_elt->next;
 829       else if (b_elt->indx < a_elt->indx)
 830         b_elt = b_elt->next;
 831       else
 832         {
 833           /* Matching elts, generate A &= ~B.  */
 834           unsigned ix;
 835           BITMAP_WORD ior = 0;
 836
 837           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 838             {
 839               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
 840               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
 841
 842               a_elt->bits[ix] = r;
 843               changed |= cleared;
 844               ior |= r;
 845             }
 846           next = a_elt->next;
 847           if (!ior)
 848             bitmap_element_free (a, a_elt);
 849           a_elt = next;
 850           b_elt = b_elt->next;
 851         }
 852     }
 853   gcc_assert (!a->current == !a->first);
 854   gcc_assert (!a->current || a->indx == a->current->indx);
 855   return changed != 0;
 856 }
 857
 858 /* Clear COUNT bits from START in HEAD.  */
 859 void
 860 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
 861 {
 862   unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
 863   unsigned int end_bit_plus1 = start + count;
 864   unsigned int end_bit = end_bit_plus1 - 1;
 865   unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
 866   bitmap_element *elt = bitmap_find_bit (head, start);
 867
 868   /* If bitmap_find_bit returns zero, the current is the closest block
 869      to the result.  If the current is less than first index, find the
 870      next one.  Otherwise, just set elt to be current.  */
 871   if (!elt)
 872     {
 873       if (head->current)
 874         {
 875           if (head->indx < first_index)
 876             {
 877               elt = head->current->next;
 878               if (!elt)
 879                 return;
 880             }
 881           else
 882             elt = head->current;
 883         }
 884       else
 885         return;
 886     }
 887
 888   while (elt && (elt->indx <= last_index))
 889     {
 890       bitmap_element * next_elt = elt->next;
 891       unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
 892       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
 893
 894
 895       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
 896         /* Get rid of the entire elt and go to the next one.  */
 897         bitmap_element_free (head, elt);
 898       else
 899         {
 900           /* Going to have to knock out some bits in this elt.  */
 901           unsigned int first_word_to_mod;
 902           BITMAP_WORD first_mask;
 903           unsigned int last_word_to_mod;
 904           BITMAP_WORD last_mask;
 905           unsigned int i;
 906           bool clear = true;
 907
 908           if (elt_start_bit <= start)
 909             {
 910               /* The first bit to turn off is somewhere inside this
 911                  elt.  */
 912               first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
 913
 914               /* This mask should have 1s in all bits >= start position. */
 915               first_mask =
 916                 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
 917               first_mask = ~first_mask;
 918             }
 919           else
 920             {
 921               /* The first bit to turn off is below this start of this elt.  */
 922               first_word_to_mod = 0;
 923               first_mask = 0;
 924               first_mask = ~first_mask;
 925             }
 926
 927           if (elt_end_bit_plus1 <= end_bit_plus1)
 928             {
 929               /* The last bit to turn off is beyond this elt.  */
 930               last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
 931               last_mask = 0;
 932               last_mask = ~last_mask;
 933             }
 934           else
 935             {
 936               /* The last bit to turn off is inside to this elt.  */
 937               last_word_to_mod =
 938                 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
 939
 940               /* The last mask should have 1s below the end bit.  */
 941               last_mask =
 942                 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
 943             }
 944
 945
 946           if (first_word_to_mod == last_word_to_mod)
 947             {
 948               BITMAP_WORD mask = first_mask & last_mask;
 949               elt->bits[first_word_to_mod] &= ~mask;
 950             }
 951           else
 952             {
 953               elt->bits[first_word_to_mod] &= ~first_mask;
 954               for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
 955                 elt->bits[i] = 0;
 956               elt->bits[last_word_to_mod] &= ~last_mask;
 957             }
 958           for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 959             if (elt->bits[i])
 960               {
 961                 clear = false;
 962                 break;
 963               }
 964           /* Check to see if there are any bits left.  */
 965           if (clear)
 966             bitmap_element_free (head, elt);
 967         }
 968       elt = next_elt;
 969     }
 970
 971   if (elt)
 972     {
 973       head->current = elt;
 974       head->indx = head->current->indx;
 975     }
 976 }
 977
 978 /* A = ~A & B. */
 979
 980 void
 981 bitmap_compl_and_into (bitmap a, bitmap b)
 982 {
 983   bitmap_element *a_elt = a->first;
 984   bitmap_element *b_elt = b->first;
 985   bitmap_element *a_prev = NULL;
 986   bitmap_element *next;
 987
 988   gcc_assert (a != b);
 989
 990   if (bitmap_empty_p (a))
 991     {
 992       bitmap_copy (a, b);
 993       return;
 994     }
 995   if (bitmap_empty_p (b))
 996     {
 997       bitmap_clear (a);
 998       return;
 999     }
1000
1001   while (a_elt || b_elt)
1002     {
1003       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1004         {
1005           /* A is before B.  Remove A */
1006           next = a_elt->next;
1007           a_prev = a_elt->prev;
1008           bitmap_element_free (a, a_elt);
1009           a_elt = next;
1010         }
1011       else if (!a_elt || b_elt->indx < a_elt->indx)
1012         {
1013           /* B is before A.  Copy B. */
1014           next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1015           memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1016           a_prev = next;
1017           b_elt = b_elt->next;
1018         }
1019       else
1020         {
1021           /* Matching elts, generate A = ~A & B.  */
1022           unsigned ix;
1023           BITMAP_WORD ior = 0;
1024
1025           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1026             {
1027               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1028               BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1029
1030               a_elt->bits[ix] = r;
1031               ior |= r;
1032             }
1033           next = a_elt->next;
1034           if (!ior)
1035             bitmap_element_free (a, a_elt);
1036           else
1037             a_prev = a_elt;
1038           a_elt = next;
1039           b_elt = b_elt->next;
1040         }
1041     }
1042   gcc_assert (!a->current == !a->first);
1043   gcc_assert (!a->current || a->indx == a->current->indx);
1044   return;
1045 }
1046
1047 /* DST = A | B.  Return true if DST changes.  */
1048
1049 bool
1050 bitmap_ior (bitmap dst, bitmap a, bitmap b)
1051 {
1052   bitmap_element *dst_elt = dst->first;
1053   bitmap_element *a_elt = a->first;
1054   bitmap_element *b_elt = b->first;
1055   bitmap_element *dst_prev = NULL;
1056   bool changed = false;
1057
1058   gcc_assert (dst != a && dst != b);
1059
1060   while (a_elt || b_elt)
1061     {
1062       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1063         {
1064           /* Matching elts, generate A | B.  */
1065           unsigned ix;
1066
1067           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1068             {
1069               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1070                 {
1071                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1072
1073                   if (r != dst_elt->bits[ix])
1074                     {
1075                       dst_elt->bits[ix] = r;
1076                       changed = true;
1077                     }
1078                 }
1079             }
1080           else
1081             {
1082               changed = true;
1083               if (!dst_elt)
1084                 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1085               else
1086                 dst_elt->indx = a_elt->indx;
1087               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1088                 {
1089                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1090
1091                   dst_elt->bits[ix] = r;
1092                 }
1093             }
1094           a_elt = a_elt->next;
1095           b_elt = b_elt->next;
1096           dst_prev = dst_elt;
1097           dst_elt = dst_elt->next;
1098         }
1099       else
1100         {
1101           /* Copy a single element.  */
1102           bitmap_element *src;
1103
1104           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1105             {
1106               src = a_elt;
1107               a_elt = a_elt->next;
1108             }
1109           else
1110             {
1111               src = b_elt;
1112               b_elt = b_elt->next;
1113             }
1114
1115           if (!changed && dst_elt && dst_elt->indx == src->indx)
1116             {
1117               unsigned ix;
1118
1119               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1120                 if (src->bits[ix] != dst_elt->bits[ix])
1121                   {
1122                     dst_elt->bits[ix] = src->bits[ix];
1123                     changed = true;
1124                   }
1125             }
1126           else
1127             {
1128               changed = true;
1129               if (!dst_elt)
1130                 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1131               else
1132                 dst_elt->indx = src->indx;
1133               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1134             }
1135
1136           dst_prev = dst_elt;
1137           dst_elt = dst_elt->next;
1138         }
1139     }
1140
1141   if (dst_elt)
1142     {
1143       changed = true;
1144       bitmap_elt_clear_from (dst, dst_elt);
1145     }
1146   gcc_assert (!dst->current == !dst->first);
1147   if (dst->current)
1148     dst->indx = dst->current->indx;
1149   return changed;
1150 }
1151
1152 /* A |= B.  Return true if A changes.  */
1153
1154 bool
1155 bitmap_ior_into (bitmap a, bitmap b)
1156 {
1157   bitmap_element *a_elt = a->first;
1158   bitmap_element *b_elt = b->first;
1159   bitmap_element *a_prev = NULL;
1160   bool changed = false;
1161
1162   if (a == b)
1163     return false;
1164
1165   while (b_elt)
1166     {
1167       if (!a_elt || b_elt->indx < a_elt->indx)
1168         {
1169           /* Copy b_elt.  */
1170           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1171           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1172           a_prev = dst;
1173           b_elt = b_elt->next;
1174           changed = true;
1175         }
1176       else if (a_elt->indx < b_elt->indx)
1177         {
1178           a_prev = a_elt;
1179           a_elt = a_elt->next;
1180         }
1181       else
1182         {
1183           /* Matching elts, generate A |= B.  */
1184           unsigned ix;
1185
1186           if (changed)
1187             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1188               {
1189                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1190
1191                 a_elt->bits[ix] = r;
1192               }
1193           else
1194             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1195               {
1196                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1197
1198                 if (a_elt->bits[ix] != r)
1199                   {
1200                     changed = true;
1201                     a_elt->bits[ix] = r;
1202                   }
1203               }
1204           b_elt = b_elt->next;
1205           a_prev = a_elt;
1206           a_elt = a_elt->next;
1207         }
1208     }
1209   gcc_assert (!a->current == !a->first);
1210   if (a->current)
1211     a->indx = a->current->indx;
1212   return changed;
1213 }
1214
1215 /* DST = A ^ B  */
1216
1217 void
1218 bitmap_xor (bitmap dst, bitmap a, bitmap b)
1219 {
1220   bitmap_element *dst_elt = dst->first;
1221   bitmap_element *a_elt = a->first;
1222   bitmap_element *b_elt = b->first;
1223   bitmap_element *dst_prev = NULL;
1224
1225   gcc_assert (dst != a && dst != b);
1226   if (a == b)
1227     {
1228       bitmap_clear (dst);
1229       return;
1230     }
1231
1232   while (a_elt || b_elt)
1233     {
1234       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1235         {
1236           /* Matching elts, generate A ^ B.  */
1237           unsigned ix;
1238           BITMAP_WORD ior = 0;
1239
1240           if (!dst_elt)
1241             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1242           else
1243             dst_elt->indx = a_elt->indx;
1244           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1245             {
1246               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1247
1248               ior |= r;
1249               dst_elt->bits[ix] = r;
1250             }
1251           a_elt = a_elt->next;
1252           b_elt = b_elt->next;
1253           if (ior)
1254             {
1255               dst_prev = dst_elt;
1256               dst_elt = dst_elt->next;
1257             }
1258         }
1259       else
1260         {
1261           /* Copy a single element.  */
1262           bitmap_element *src;
1263
1264           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1265             {
1266               src = a_elt;
1267               a_elt = a_elt->next;
1268             }
1269           else
1270             {
1271               src = b_elt;
1272               b_elt = b_elt->next;
1273             }
1274
1275           if (!dst_elt)
1276             dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1277           else
1278             dst_elt->indx = src->indx;
1279           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1280           dst_prev = dst_elt;
1281           dst_elt = dst_elt->next;
1282         }
1283     }
1284   bitmap_elt_clear_from (dst, dst_elt);
1285   gcc_assert (!dst->current == !dst->first);
1286   if (dst->current)
1287     dst->indx = dst->current->indx;
1288 }
1289
1290 /* A ^= B */
1291
1292 void
1293 bitmap_xor_into (bitmap a, bitmap b)
1294 {
1295   bitmap_element *a_elt = a->first;
1296   bitmap_element *b_elt = b->first;
1297   bitmap_element *a_prev = NULL;
1298
1299   if (a == b)
1300     {
1301       bitmap_clear (a);
1302       return;
1303     }
1304
1305   while (b_elt)
1306     {
1307       if (!a_elt || b_elt->indx < a_elt->indx)
1308         {
1309           /* Copy b_elt.  */
1310           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1311           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1312           a_prev = dst;
1313           b_elt = b_elt->next;
1314         }
1315       else if (a_elt->indx < b_elt->indx)
1316         {
1317           a_prev = a_elt;
1318           a_elt = a_elt->next;
1319         }
1320       else
1321         {
1322           /* Matching elts, generate A ^= B.  */
1323           unsigned ix;
1324           BITMAP_WORD ior = 0;
1325           bitmap_element *next = a_elt->next;
1326
1327           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1328             {
1329               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1330
1331               ior |= r;
1332               a_elt->bits[ix] = r;
1333             }
1334           b_elt = b_elt->next;
1335           if (ior)
1336             a_prev = a_elt;
1337           else
1338             bitmap_element_free (a, a_elt);
1339           a_elt = next;
1340         }
1341     }
1342   gcc_assert (!a->current == !a->first);
1343   if (a->current)
1344     a->indx = a->current->indx;
1345 }
1346
1347 /* Return true if two bitmaps are identical.
1348    We do not bother with a check for pointer equality, as that never
1349    occurs in practice.  */
1350
1351 bool
1352 bitmap_equal_p (bitmap a, bitmap b)
1353 {
1354   bitmap_element *a_elt;
1355   bitmap_element *b_elt;
1356   unsigned ix;
1357
1358   for (a_elt = a->first, b_elt = b->first;
1359        a_elt && b_elt;
1360        a_elt = a_elt->next, b_elt = b_elt->next)
1361     {
1362       if (a_elt->indx != b_elt->indx)
1363         return false;
1364       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1365         if (a_elt->bits[ix] != b_elt->bits[ix])
1366           return false;
1367     }
1368   return !a_elt && !b_elt;
1369 }
1370
1371 /* Return true if A AND B is not empty.  */
1372
1373 bool
1374 bitmap_intersect_p (bitmap a, bitmap b)
1375 {
1376   bitmap_element *a_elt;
1377   bitmap_element *b_elt;
1378   unsigned ix;
1379
1380   for (a_elt = a->first, b_elt = b->first;
1381        a_elt && b_elt;)
1382     {
1383       if (a_elt->indx < b_elt->indx)
1384         a_elt = a_elt->next;
1385       else if (b_elt->indx < a_elt->indx)
1386         b_elt = b_elt->next;
1387       else
1388         {
1389           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1390             if (a_elt->bits[ix] & b_elt->bits[ix])
1391               return true;
1392           a_elt = a_elt->next;
1393           b_elt = b_elt->next;
1394         }
1395     }
1396   return false;
1397 }
1398
1399 /* Return true if A AND NOT B is not empty.  */
1400
1401 bool
1402 bitmap_intersect_compl_p (bitmap a, bitmap b)
1403 {
1404   bitmap_element *a_elt;
1405   bitmap_element *b_elt;
1406   unsigned ix;
1407   for (a_elt = a->first, b_elt = b->first;
1408        a_elt && b_elt;)
1409     {
1410       if (a_elt->indx < b_elt->indx)
1411         return true;
1412       else if (b_elt->indx < a_elt->indx)
1413         b_elt = b_elt->next;
1414       else
1415         {
1416           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1417             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1418               return true;
1419           a_elt = a_elt->next;
1420           b_elt = b_elt->next;
1421         }
1422     }
1423   return a_elt != NULL;
1424 }
1425
1426 \f
1427 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1428
1429 bool
1430 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1431 {
1432   bitmap_head tmp;
1433   bool changed;
1434
1435   bitmap_initialize (&tmp, &bitmap_default_obstack);
1436   bitmap_and_compl (&tmp, from1, from2);
1437   changed = bitmap_ior (dst, a, &tmp);
1438   bitmap_clear (&tmp);
1439
1440   return changed;
1441 }
1442
1443 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1444
1445 bool
1446 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1447 {
1448   bitmap_head tmp;
1449   bool changed;
1450
1451   bitmap_initialize (&tmp, &bitmap_default_obstack);
1452   bitmap_and_compl (&tmp, from1, from2);
1453   changed = bitmap_ior_into (a, &tmp);
1454   bitmap_clear (&tmp);
1455
1456   return changed;
1457 }
1458 \f
1459 /* Debugging function to print out the contents of a bitmap.  */
1460
1461 void
1462 debug_bitmap_file (FILE *file, bitmap head)
1463 {
1464   bitmap_element *ptr;
1465
1466   fprintf (file, "\nfirst = %p current = %p indx = %u\n",
1467            (void *) head->first, (void *) head->current, head->indx);
1468
1469   for (ptr = head->first; ptr; ptr = ptr->next)
1470     {
1471       unsigned int i, j, col = 26;
1472
1473       fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1474                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1475
1476       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1477         for (j = 0; j < BITMAP_WORD_BITS; j++)
1478           if ((ptr->bits[i] >> j) & 1)
1479             {
1480               if (col > 70)
1481                 {
1482                   fprintf (file, "\n\t\t\t");
1483                   col = 24;
1484                 }
1485
1486               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1487                                      + i * BITMAP_WORD_BITS + j));
1488               col += 4;
1489             }
1490
1491       fprintf (file, " }\n");
1492     }
1493 }
1494
1495 /* Function to be called from the debugger to print the contents
1496    of a bitmap.  */
1497
1498 void
1499 debug_bitmap (bitmap head)
1500 {
1501   debug_bitmap_file (stdout, head);
1502 }
1503
1504 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1505    it does not print anything but the bits.  */
1506
1507 void
1508 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1509 {
1510   const char *comma = "";
1511   unsigned i;
1512   bitmap_iterator bi;
1513
1514   fputs (prefix, file);
1515   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1516     {
1517       fprintf (file, "%s%d", comma, i);
1518       comma = ", ";
1519     }
1520   fputs (suffix, file);
1521 }
1522
1523 /* Compute hash of bitmap (for purposes of hashing).  */
1524 hashval_t
1525 bitmap_hash (bitmap head)
1526 {
1527   bitmap_element *ptr;
1528   BITMAP_WORD hash = 0;
1529   int ix;
1530
1531   for (ptr = head->first; ptr; ptr = ptr->next)
1532     {
1533       hash ^= ptr->indx;
1534       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1535         hash ^= ptr->bits[ix];
1536     }
1537   return (hashval_t)hash;
1538 }
1539
1540 #include "gt-bitmap.h"