gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
   3    2006, 2007, 2008, 2009, 2010 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "obstack.h"
  25 #include "ggc.h"
  26 #include "bitmap.h"
  27 #include "hashtab.h"
  28
  29 #ifdef GATHER_STATISTICS
  30
  31 /* Store information about each particular bitmap.  */
  32 struct bitmap_descriptor
  33 {
  34   const char *function;
  35   const char *file;
  36   int line;
  37   int created;
  38   HOST_WIDEST_INT allocated;
  39   HOST_WIDEST_INT peak;
  40   HOST_WIDEST_INT current;
  41   int nsearches;
  42   int search_iter;
  43 };
  44
  45 /* Hashtable mapping bitmap names to descriptors.  */
  46 static htab_t bitmap_desc_hash;
  47
  48 /* Hashtable helpers.  */
  49 static hashval_t
  50 hash_descriptor (const void *p)
  51 {
  52   const struct bitmap_descriptor *const d =
  53     (const struct bitmap_descriptor *) p;
  54   return htab_hash_pointer (d->file) + d->line;
  55 }
  56 struct loc
  57 {
  58   const char *file;
  59   const char *function;
  60   int line;
  61 };
  62 static int
  63 eq_descriptor (const void *p1, const void *p2)
  64 {
  65   const struct bitmap_descriptor *const d =
  66     (const struct bitmap_descriptor *) p1;
  67   const struct loc *const l = (const struct loc *) p2;
  68   return d->file == l->file && d->function == l->function && d->line == l->line;
  69 }
  70
  71 /* For given file and line, return descriptor, create new if needed.  */
  72 static struct bitmap_descriptor *
  73 bitmap_descriptor (const char *file, const char *function, int line)
  74 {
  75   struct bitmap_descriptor **slot;
  76   struct loc loc;
  77
  78   loc.file = file;
  79   loc.function = function;
  80   loc.line = line;
  81
  82   if (!bitmap_desc_hash)
  83     bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
  84
  85   slot = (struct bitmap_descriptor **)
  86     htab_find_slot_with_hash (bitmap_desc_hash, &loc,
  87                               htab_hash_pointer (file) + line,
  88                               INSERT);
  89   if (*slot)
  90     return *slot;
  91   *slot = XCNEW (struct bitmap_descriptor);
  92   (*slot)->file = file;
  93   (*slot)->function = function;
  94   (*slot)->line = line;
  95   return *slot;
  96 }
  97
  98 /* Register new bitmap.  */
  99 void
 100 bitmap_register (bitmap b MEM_STAT_DECL)
 101 {
 102   b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line);
 103   b->desc->created++;
 104 }
 105
 106 /* Account the overhead.  */
 107 static void
 108 register_overhead (bitmap b, int amount)
 109 {
 110   b->desc->current += amount;
 111   if (amount > 0)
 112     b->desc->allocated += amount;
 113   gcc_assert (b->desc->current >= 0);
 114   if (b->desc->peak < b->desc->current)
 115     b->desc->peak = b->desc->current;
 116 }
 117 #endif
 118
 119 /* Global data */
 120 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
 121 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
 122 static int bitmap_default_obstack_depth;
 123 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
 124                                                             GC'd elements.  */
 125
 126 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
 127 static void bitmap_element_free (bitmap, bitmap_element *);
 128 static bitmap_element *bitmap_element_allocate (bitmap);
 129 static int bitmap_element_zerop (const bitmap_element *);
 130 static void bitmap_element_link (bitmap, bitmap_element *);
 131 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
 132 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
 133 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
 134 \f
 135
 136 /* Add ELEM to the appropriate freelist.  */
 137 static inline void
 138 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 139 {
 140   bitmap_obstack *bit_obstack = head->obstack;
 141
 142   elt->next = NULL;
 143   if (bit_obstack)
 144     {
 145       elt->prev = bit_obstack->elements;
 146       bit_obstack->elements = elt;
 147     }
 148   else
 149     {
 150       elt->prev = bitmap_ggc_free;
 151       bitmap_ggc_free = elt;
 152     }
 153 }
 154
 155 /* Free a bitmap element.  Since these are allocated off the
 156    bitmap_obstack, "free" actually means "put onto the freelist".  */
 157
 158 static inline void
 159 bitmap_element_free (bitmap head, bitmap_element *elt)
 160 {
 161   bitmap_element *next = elt->next;
 162   bitmap_element *prev = elt->prev;
 163
 164   if (prev)
 165     prev->next = next;
 166
 167   if (next)
 168     next->prev = prev;
 169
 170   if (head->first == elt)
 171     head->first = next;
 172
 173   /* Since the first thing we try is to insert before current,
 174      make current the next entry in preference to the previous.  */
 175   if (head->current == elt)
 176     {
 177       head->current = next != 0 ? next : prev;
 178       if (head->current)
 179         head->indx = head->current->indx;
 180       else
 181         head->indx = 0;
 182     }
 183 #ifdef GATHER_STATISTICS
 184   register_overhead (head, -((int)sizeof (bitmap_element)));
 185 #endif
 186   bitmap_elem_to_freelist (head, elt);
 187 }
 188 \f
 189 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 190
 191 static inline bitmap_element *
 192 bitmap_element_allocate (bitmap head)
 193 {
 194   bitmap_element *element;
 195   bitmap_obstack *bit_obstack = head->obstack;
 196
 197   if (bit_obstack)
 198     {
 199       element = bit_obstack->elements;
 200
 201       if (element)
 202         /* Use up the inner list first before looking at the next
 203            element of the outer list.  */
 204         if (element->next)
 205           {
 206             bit_obstack->elements = element->next;
 207             bit_obstack->elements->prev = element->prev;
 208           }
 209         else
 210           /*  Inner list was just a singleton.  */
 211           bit_obstack->elements = element->prev;
 212       else
 213         element = XOBNEW (&bit_obstack->obstack, bitmap_element);
 214     }
 215   else
 216     {
 217       element = bitmap_ggc_free;
 218       if (element)
 219         /* Use up the inner list first before looking at the next
 220            element of the outer list.  */
 221         if (element->next)
 222           {
 223             bitmap_ggc_free = element->next;
 224             bitmap_ggc_free->prev = element->prev;
 225           }
 226         else
 227           /*  Inner list was just a singleton.  */
 228           bitmap_ggc_free = element->prev;
 229       else
 230         element = ggc_alloc_bitmap_element_def ();
 231     }
 232
 233 #ifdef GATHER_STATISTICS
 234   register_overhead (head, sizeof (bitmap_element));
 235 #endif
 236   memset (element->bits, 0, sizeof (element->bits));
 237
 238   return element;
 239 }
 240
 241 /* Remove ELT and all following elements from bitmap HEAD.  */
 242
 243 void
 244 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 245 {
 246   bitmap_element *prev;
 247   bitmap_obstack *bit_obstack = head->obstack;
 248 #ifdef GATHER_STATISTICS
 249   int n;
 250 #endif
 251
 252   if (!elt) return;
 253 #ifdef GATHER_STATISTICS
 254   n = 0;
 255   for (prev = elt; prev; prev = prev->next)
 256     n++;
 257   register_overhead (head, -sizeof (bitmap_element) * n);
 258 #endif
 259
 260   prev = elt->prev;
 261   if (prev)
 262     {
 263       prev->next = NULL;
 264       if (head->current->indx > prev->indx)
 265         {
 266           head->current = prev;
 267           head->indx = prev->indx;
 268         }
 269     }
 270   else
 271     {
 272       head->first = NULL;
 273       head->current = NULL;
 274       head->indx = 0;
 275     }
 276
 277   /* Put the entire list onto the free list in one operation. */
 278   if (bit_obstack)
 279     {
 280       elt->prev = bit_obstack->elements;
 281       bit_obstack->elements = elt;
 282     }
 283   else
 284     {
 285       elt->prev = bitmap_ggc_free;
 286       bitmap_ggc_free = elt;
 287     }
 288 }
 289
 290 /* Clear a bitmap by freeing the linked list.  */
 291
 292 void
 293 bitmap_clear (bitmap head)
 294 {
 295   if (head->first)
 296     bitmap_elt_clear_from (head, head->first);
 297 }
 298 \f
 299 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
 300    the default bitmap obstack.  */
 301
 302 void
 303 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
 304 {
 305   if (!bit_obstack)
 306     {
 307       if (bitmap_default_obstack_depth++)
 308         return;
 309       bit_obstack = &bitmap_default_obstack;
 310     }
 311
 312 #if !defined(__GNUC__) || (__GNUC__ < 2)
 313 #define __alignof__(type) 0
 314 #endif
 315
 316   bit_obstack->elements = NULL;
 317   bit_obstack->heads = NULL;
 318   obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
 319                               __alignof__ (bitmap_element),
 320                               obstack_chunk_alloc,
 321                               obstack_chunk_free);
 322 }
 323
 324 /* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
 325    release the default bitmap obstack.  */
 326
 327 void
 328 bitmap_obstack_release (bitmap_obstack *bit_obstack)
 329 {
 330   if (!bit_obstack)
 331     {
 332       if (--bitmap_default_obstack_depth)
 333         {
 334           gcc_assert (bitmap_default_obstack_depth > 0);
 335           return;
 336         }
 337       bit_obstack = &bitmap_default_obstack;
 338     }
 339
 340   bit_obstack->elements = NULL;
 341   bit_obstack->heads = NULL;
 342   obstack_free (&bit_obstack->obstack, NULL);
 343 }
 344
 345 /* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
 346    it on the default bitmap obstack.  */
 347
 348 bitmap
 349 bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
 350 {
 351   bitmap map;
 352
 353   if (!bit_obstack)
 354     bit_obstack = &bitmap_default_obstack;
 355   map = bit_obstack->heads;
 356   if (map)
 357     bit_obstack->heads = (struct bitmap_head_def *) map->first;
 358   else
 359     map = XOBNEW (&bit_obstack->obstack, bitmap_head);
 360   bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
 361 #ifdef GATHER_STATISTICS
 362   register_overhead (map, sizeof (bitmap_head));
 363 #endif
 364
 365   return map;
 366 }
 367
 368 /* Create a new GCd bitmap.  */
 369
 370 bitmap
 371 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
 372 {
 373   bitmap map;
 374
 375   map = ggc_alloc_bitmap_head_def ();
 376   bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
 377 #ifdef GATHER_STATISTICS
 378   register_overhead (map, sizeof (bitmap_head));
 379 #endif
 380
 381   return map;
 382 }
 383
 384 /* Release an obstack allocated bitmap.  */
 385
 386 void
 387 bitmap_obstack_free (bitmap map)
 388 {
 389   if (map)
 390     {
 391       bitmap_clear (map);
 392       map->first = (bitmap_element *) map->obstack->heads;
 393 #ifdef GATHER_STATISTICS
 394       register_overhead (map, -((int)sizeof (bitmap_head)));
 395 #endif
 396       map->obstack->heads = map;
 397     }
 398 }
 399
 400 \f
 401 /* Return nonzero if all bits in an element are zero.  */
 402
 403 static inline int
 404 bitmap_element_zerop (const bitmap_element *element)
 405 {
 406 #if BITMAP_ELEMENT_WORDS == 2
 407   return (element->bits[0] | element->bits[1]) == 0;
 408 #else
 409   unsigned i;
 410
 411   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 412     if (element->bits[i] != 0)
 413       return 0;
 414
 415   return 1;
 416 #endif
 417 }
 418 \f
 419 /* Link the bitmap element into the current bitmap linked list.  */
 420
 421 static inline void
 422 bitmap_element_link (bitmap head, bitmap_element *element)
 423 {
 424   unsigned int indx = element->indx;
 425   bitmap_element *ptr;
 426
 427   /* If this is the first and only element, set it in.  */
 428   if (head->first == 0)
 429     {
 430       element->next = element->prev = 0;
 431       head->first = element;
 432     }
 433
 434   /* If this index is less than that of the current element, it goes someplace
 435      before the current element.  */
 436   else if (indx < head->indx)
 437     {
 438       for (ptr = head->current;
 439            ptr->prev != 0 && ptr->prev->indx > indx;
 440            ptr = ptr->prev)
 441         ;
 442
 443       if (ptr->prev)
 444         ptr->prev->next = element;
 445       else
 446         head->first = element;
 447
 448       element->prev = ptr->prev;
 449       element->next = ptr;
 450       ptr->prev = element;
 451     }
 452
 453   /* Otherwise, it must go someplace after the current element.  */
 454   else
 455     {
 456       for (ptr = head->current;
 457            ptr->next != 0 && ptr->next->indx < indx;
 458            ptr = ptr->next)
 459         ;
 460
 461       if (ptr->next)
 462         ptr->next->prev = element;
 463
 464       element->next = ptr->next;
 465       element->prev = ptr;
 466       ptr->next = element;
 467     }
 468
 469   /* Set up so this is the first element searched.  */
 470   head->current = element;
 471   head->indx = indx;
 472 }
 473
 474 /* Insert a new uninitialized element into bitmap HEAD after element
 475    ELT.  If ELT is NULL, insert the element at the start.  Return the
 476    new element.  */
 477
 478 static bitmap_element *
 479 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
 480 {
 481   bitmap_element *node = bitmap_element_allocate (head);
 482   node->indx = indx;
 483
 484   if (!elt)
 485     {
 486       if (!head->current)
 487         {
 488           head->current = node;
 489           head->indx = indx;
 490         }
 491       node->next = head->first;
 492       if (node->next)
 493         node->next->prev = node;
 494       head->first = node;
 495       node->prev = NULL;
 496     }
 497   else
 498     {
 499       gcc_checking_assert (head->current);
 500       node->next = elt->next;
 501       if (node->next)
 502         node->next->prev = node;
 503       elt->next = node;
 504       node->prev = elt;
 505     }
 506   return node;
 507 }
 508 \f
 509 /* Copy a bitmap to another bitmap.  */
 510
 511 void
 512 bitmap_copy (bitmap to, const_bitmap from)
 513 {
 514   const bitmap_element *from_ptr;
 515   bitmap_element *to_ptr = 0;
 516
 517   bitmap_clear (to);
 518
 519   /* Copy elements in forward direction one at a time.  */
 520   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 521     {
 522       bitmap_element *to_elt = bitmap_element_allocate (to);
 523
 524       to_elt->indx = from_ptr->indx;
 525       memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits));
 526
 527       /* Here we have a special case of bitmap_element_link, for the case
 528          where we know the links are being entered in sequence.  */
 529       if (to_ptr == 0)
 530         {
 531           to->first = to->current = to_elt;
 532           to->indx = from_ptr->indx;
 533           to_elt->next = to_elt->prev = 0;
 534         }
 535       else
 536         {
 537           to_elt->prev = to_ptr;
 538           to_elt->next = 0;
 539           to_ptr->next = to_elt;
 540         }
 541
 542       to_ptr = to_elt;
 543     }
 544 }
 545 \f
 546 /* Find a bitmap element that would hold a bitmap's bit.
 547    Update the `current' field even if we can't find an element that
 548    would hold the bitmap's bit to make eventual allocation
 549    faster.  */
 550
 551 static inline bitmap_element *
 552 bitmap_find_bit (bitmap head, unsigned int bit)
 553 {
 554   bitmap_element *element;
 555   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 556
 557   if (head->current == 0
 558       || head->indx == indx)
 559     return head->current;
 560 #ifdef GATHER_STATISTICS
 561   head->desc->nsearches++;
 562 #endif
 563
 564   if (head->indx < indx)
 565     /* INDX is beyond head->indx.  Search from head->current
 566        forward.  */
 567     for (element = head->current;
 568          element->next != 0 && element->indx < indx;
 569          element = element->next)
 570 #ifdef GATHER_STATISTICS
 571       head->desc->search_iter++;
 572 #else
 573       ;
 574 #endif
 575
 576   else if (head->indx / 2 < indx)
 577     /* INDX is less than head->indx and closer to head->indx than to
 578        0.  Search from head->current backward.  */
 579     for (element = head->current;
 580          element->prev != 0 && element->indx > indx;
 581          element = element->prev)
 582 #ifdef GATHER_STATISTICS
 583       head->desc->search_iter++;
 584 #else
 585       ;
 586 #endif
 587
 588   else
 589     /* INDX is less than head->indx and closer to 0 than to
 590        head->indx.  Search from head->first forward.  */
 591     for (element = head->first;
 592          element->next != 0 && element->indx < indx;
 593          element = element->next)
 594 #ifdef GATHER_STATISTICS
 595       head->desc->search_iter++;
 596 #else
 597       ;
 598 #endif
 599
 600   /* `element' is the nearest to the one we want.  If it's not the one we
 601      want, the one we want doesn't exist.  */
 602   head->current = element;
 603   head->indx = element->indx;
 604   if (element != 0 && element->indx != indx)
 605     element = 0;
 606
 607   return element;
 608 }
 609 \f
 610 /* Clear a single bit in a bitmap.  Return true if the bit changed.  */
 611
 612 bool
 613 bitmap_clear_bit (bitmap head, int bit)
 614 {
 615   bitmap_element *const ptr = bitmap_find_bit (head, bit);
 616
 617   if (ptr != 0)
 618     {
 619       unsigned bit_num  = bit % BITMAP_WORD_BITS;
 620       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 621       BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 622       bool res = (ptr->bits[word_num] & bit_val) != 0;
 623       if (res)
 624         {
 625           ptr->bits[word_num] &= ~bit_val;
 626           /* If we cleared the entire word, free up the element.  */
 627           if (!ptr->bits[word_num]
 628               && bitmap_element_zerop (ptr))
 629             bitmap_element_free (head, ptr);
 630         }
 631
 632       return res;
 633     }
 634
 635   return false;
 636 }
 637
 638 /* Set a single bit in a bitmap.  Return true if the bit changed.  */
 639
 640 bool
 641 bitmap_set_bit (bitmap head, int bit)
 642 {
 643   bitmap_element *ptr = bitmap_find_bit (head, bit);
 644   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 645   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 646   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 647
 648   if (ptr == 0)
 649     {
 650       ptr = bitmap_element_allocate (head);
 651       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 652       ptr->bits[word_num] = bit_val;
 653       bitmap_element_link (head, ptr);
 654       return true;
 655     }
 656   else
 657     {
 658       bool res = (ptr->bits[word_num] & bit_val) == 0;
 659       if (res)
 660         ptr->bits[word_num] |= bit_val;
 661       return res;
 662     }
 663 }
 664
 665 /* Return whether a bit is set within a bitmap.  */
 666
 667 int
 668 bitmap_bit_p (bitmap head, int bit)
 669 {
 670   bitmap_element *ptr;
 671   unsigned bit_num;
 672   unsigned word_num;
 673
 674   ptr = bitmap_find_bit (head, bit);
 675   if (ptr == 0)
 676     return 0;
 677
 678   bit_num = bit % BITMAP_WORD_BITS;
 679   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 680
 681   return (ptr->bits[word_num] >> bit_num) & 1;
 682 }
 683 \f
 684 #if GCC_VERSION < 3400
 685 /* Table of number of set bits in a character, indexed by value of char.  */
 686 static const unsigned char popcount_table[] =
 687 {
 688     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,
 689     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,
 690     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,
 691     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,
 692     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,
 693     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,
 694     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,
 695     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,
 696 };
 697
 698 static unsigned long
 699 bitmap_popcount (BITMAP_WORD a)
 700 {
 701   unsigned long ret = 0;
 702   unsigned i;
 703
 704   /* Just do this the table way for now  */
 705   for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
 706     ret += popcount_table[(a >> i) & 0xff];
 707   return ret;
 708 }
 709 #endif
 710 /* Count the number of bits set in the bitmap, and return it.  */
 711
 712 unsigned long
 713 bitmap_count_bits (const_bitmap a)
 714 {
 715   unsigned long count = 0;
 716   const bitmap_element *elt;
 717   unsigned ix;
 718
 719   for (elt = a->first; elt; elt = elt->next)
 720     {
 721       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 722         {
 723 #if GCC_VERSION >= 3400
 724           /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 725          of BITMAP_WORD is not material.  */
 726           count += __builtin_popcountl (elt->bits[ix]);
 727 #else
 728           count += bitmap_popcount (elt->bits[ix]);
 729 #endif
 730         }
 731     }
 732   return count;
 733 }
 734
 735 /* Return true if the bitmap has a single bit set.  Otherwise return
 736    false.  */
 737
 738 bool
 739 bitmap_single_bit_set_p (const_bitmap a)
 740 {
 741   unsigned long count = 0;
 742   const bitmap_element *elt;
 743   unsigned ix;
 744
 745   if (bitmap_empty_p (a))
 746     return false;
 747
 748   elt = a->first;
 749   /* As there are no completely empty bitmap elements, a second one
 750      means we have more than one bit set.  */
 751   if (elt->next != NULL)
 752     return false;
 753
 754   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 755     {
 756 #if GCC_VERSION >= 3400
 757       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 758          of BITMAP_WORD is not material.  */
 759       count += __builtin_popcountl (elt->bits[ix]);
 760 #else
 761       count += bitmap_popcount (elt->bits[ix]);
 762 #endif
 763       if (count > 1)
 764         return false;
 765     }
 766
 767   return count == 1;
 768 }
 769
 770
 771 /* Return the bit number of the first set bit in the bitmap.  The
 772    bitmap must be non-empty.  */
 773
 774 unsigned
 775 bitmap_first_set_bit (const_bitmap a)
 776 {
 777   const bitmap_element *elt = a->first;
 778   unsigned bit_no;
 779   BITMAP_WORD word;
 780   unsigned ix;
 781
 782   gcc_checking_assert (elt);
 783   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 784   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 785     {
 786       word = elt->bits[ix];
 787       if (word)
 788         goto found_bit;
 789     }
 790   gcc_unreachable ();
 791  found_bit:
 792   bit_no += ix * BITMAP_WORD_BITS;
 793
 794 #if GCC_VERSION >= 3004
 795   gcc_assert (sizeof(long) == sizeof (word));
 796   bit_no += __builtin_ctzl (word);
 797 #else
 798   /* Binary search for the first set bit.  */
 799 #if BITMAP_WORD_BITS > 64
 800 #error "Fill out the table."
 801 #endif
 802 #if BITMAP_WORD_BITS > 32
 803   if (!(word & 0xffffffff))
 804     word >>= 32, bit_no += 32;
 805 #endif
 806   if (!(word & 0xffff))
 807     word >>= 16, bit_no += 16;
 808   if (!(word & 0xff))
 809     word >>= 8, bit_no += 8;
 810   if (!(word & 0xf))
 811     word >>= 4, bit_no += 4;
 812   if (!(word & 0x3))
 813     word >>= 2, bit_no += 2;
 814   if (!(word & 0x1))
 815     word >>= 1, bit_no += 1;
 816
 817  gcc_checking_assert (word & 1);
 818 #endif
 819  return bit_no;
 820 }
 821
 822 /* Return the bit number of the first set bit in the bitmap.  The
 823    bitmap must be non-empty.  */
 824
 825 unsigned
 826 bitmap_last_set_bit (const_bitmap a)
 827 {
 828   const bitmap_element *elt = a->current ? a->current : a->first;
 829   unsigned bit_no;
 830   BITMAP_WORD word;
 831   int ix;
 832
 833   gcc_checking_assert (elt);
 834   while (elt->next)
 835     elt = elt->next;
 836   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 837   for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
 838     {
 839       word = elt->bits[ix];
 840       if (word)
 841         goto found_bit;
 842     }
 843   gcc_unreachable ();
 844  found_bit:
 845   bit_no += ix * BITMAP_WORD_BITS;
 846
 847   /* Binary search for the last set bit.  */
 848 #if GCC_VERSION >= 3004
 849   gcc_assert (sizeof(long) == sizeof (word));
 850   bit_no += sizeof (long) * 8 - __builtin_ctzl (word);
 851 #else
 852 #if BITMAP_WORD_BITS > 64
 853 #error "Fill out the table."
 854 #endif
 855 #if BITMAP_WORD_BITS > 32
 856   if ((word & 0xffffffff00000000))
 857     word >>= 32, bit_no += 32;
 858 #endif
 859   if (word & 0xffff0000)
 860     word >>= 16, bit_no += 16;
 861   if (!(word & 0xff00))
 862     word >>= 8, bit_no += 8;
 863   if (!(word & 0xf0))
 864     word >>= 4, bit_no += 4;
 865   if (!(word & 12))
 866     word >>= 2, bit_no += 2;
 867   if (!(word & 2))
 868     word >>= 1, bit_no += 1;
 869 #endif
 870
 871  gcc_checking_assert (word & 1);
 872  return bit_no;
 873 }
 874 \f
 875
 876 /* DST = A & B.  */
 877
 878 void
 879 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
 880 {
 881   bitmap_element *dst_elt = dst->first;
 882   const bitmap_element *a_elt = a->first;
 883   const bitmap_element *b_elt = b->first;
 884   bitmap_element *dst_prev = NULL;
 885
 886   gcc_assert (dst != a && dst != b);
 887
 888   if (a == b)
 889     {
 890       bitmap_copy (dst, a);
 891       return;
 892     }
 893
 894   while (a_elt && b_elt)
 895     {
 896       if (a_elt->indx < b_elt->indx)
 897         a_elt = a_elt->next;
 898       else if (b_elt->indx < a_elt->indx)
 899         b_elt = b_elt->next;
 900       else
 901         {
 902           /* Matching elts, generate A & B.  */
 903           unsigned ix;
 904           BITMAP_WORD ior = 0;
 905
 906           if (!dst_elt)
 907             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 908           else
 909             dst_elt->indx = a_elt->indx;
 910           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 911             {
 912               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 913
 914               dst_elt->bits[ix] = r;
 915               ior |= r;
 916             }
 917           if (ior)
 918             {
 919               dst_prev = dst_elt;
 920               dst_elt = dst_elt->next;
 921             }
 922           a_elt = a_elt->next;
 923           b_elt = b_elt->next;
 924         }
 925     }
 926   /* Ensure that dst->current is valid.  */
 927   dst->current = dst->first;
 928   bitmap_elt_clear_from (dst, dst_elt);
 929   gcc_checking_assert (!dst->current == !dst->first);
 930   if (dst->current)
 931     dst->indx = dst->current->indx;
 932 }
 933
 934 /* A &= B.  */
 935
 936 void
 937 bitmap_and_into (bitmap a, const_bitmap b)
 938 {
 939   bitmap_element *a_elt = a->first;
 940   const bitmap_element *b_elt = b->first;
 941   bitmap_element *next;
 942
 943   if (a == b)
 944     return;
 945
 946   while (a_elt && b_elt)
 947     {
 948       if (a_elt->indx < b_elt->indx)
 949         {
 950           next = a_elt->next;
 951           bitmap_element_free (a, a_elt);
 952           a_elt = next;
 953         }
 954       else if (b_elt->indx < a_elt->indx)
 955         b_elt = b_elt->next;
 956       else
 957         {
 958           /* Matching elts, generate A &= B.  */
 959           unsigned ix;
 960           BITMAP_WORD ior = 0;
 961
 962           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 963             {
 964               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 965
 966               a_elt->bits[ix] = r;
 967               ior |= r;
 968             }
 969           next = a_elt->next;
 970           if (!ior)
 971             bitmap_element_free (a, a_elt);
 972           a_elt = next;
 973           b_elt = b_elt->next;
 974         }
 975     }
 976   bitmap_elt_clear_from (a, a_elt);
 977   gcc_checking_assert (!a->current == !a->first
 978                        && (!a->current || a->indx == a->current->indx));
 979 }
 980
 981
 982 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
 983    if non-NULL.  CHANGED is true if the destination bitmap had already been
 984    changed; the new value of CHANGED is returned.  */
 985
 986 static inline bool
 987 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
 988                  const bitmap_element *src_elt, bool changed)
 989 {
 990   if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
 991     {
 992       unsigned ix;
 993
 994       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 995         if (src_elt->bits[ix] != dst_elt->bits[ix])
 996           {
 997             dst_elt->bits[ix] = src_elt->bits[ix];
 998             changed = true;
 999           }
1000     }
1001   else
1002     {
1003       changed = true;
1004       if (!dst_elt)
1005         dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
1006       else
1007         dst_elt->indx = src_elt->indx;
1008       memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1009     }
1010   return changed;
1011 }
1012
1013
1014
1015 /* DST = A & ~B  */
1016
1017 bool
1018 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1019 {
1020   bitmap_element *dst_elt = dst->first;
1021   const bitmap_element *a_elt = a->first;
1022   const bitmap_element *b_elt = b->first;
1023   bitmap_element *dst_prev = NULL;
1024   bitmap_element **dst_prev_pnext = &dst->first;
1025   bool changed = false;
1026
1027   gcc_assert (dst != a && dst != b);
1028
1029   if (a == b)
1030     {
1031       changed = !bitmap_empty_p (dst);
1032       bitmap_clear (dst);
1033       return changed;
1034     }
1035
1036   while (a_elt)
1037     {
1038       while (b_elt && b_elt->indx < a_elt->indx)
1039         b_elt = b_elt->next;
1040
1041       if (!b_elt || b_elt->indx > a_elt->indx)
1042         {
1043           changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1044           dst_prev = *dst_prev_pnext;
1045           dst_prev_pnext = &dst_prev->next;
1046           dst_elt = *dst_prev_pnext;
1047           a_elt = a_elt->next;
1048         }
1049
1050       else
1051         {
1052           /* Matching elts, generate A & ~B.  */
1053           unsigned ix;
1054           BITMAP_WORD ior = 0;
1055
1056           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1057             {
1058               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1059                 {
1060                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1061
1062                   if (dst_elt->bits[ix] != r)
1063                     {
1064                       changed = true;
1065                       dst_elt->bits[ix] = r;
1066                     }
1067                   ior |= r;
1068                 }
1069             }
1070           else
1071             {
1072               bool new_element;
1073               if (!dst_elt || dst_elt->indx > a_elt->indx)
1074                 {
1075                   dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1076                   new_element = true;
1077                 }
1078               else
1079                 {
1080                   dst_elt->indx = a_elt->indx;
1081                   new_element = false;
1082                 }
1083
1084               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1085                 {
1086                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1087
1088                   dst_elt->bits[ix] = r;
1089                   ior |= r;
1090                 }
1091
1092               if (ior)
1093                 changed = true;
1094               else
1095                 {
1096                   changed |= !new_element;
1097                   bitmap_element_free (dst, dst_elt);
1098                   dst_elt = *dst_prev_pnext;
1099                 }
1100             }
1101
1102           if (ior)
1103             {
1104               dst_prev = *dst_prev_pnext;
1105               dst_prev_pnext = &dst_prev->next;
1106               dst_elt = *dst_prev_pnext;
1107             }
1108           a_elt = a_elt->next;
1109           b_elt = b_elt->next;
1110         }
1111     }
1112
1113   /* Ensure that dst->current is valid.  */
1114   dst->current = dst->first;
1115
1116   if (dst_elt)
1117     {
1118       changed = true;
1119       bitmap_elt_clear_from (dst, dst_elt);
1120     }
1121   gcc_checking_assert (!dst->current == !dst->first);
1122   if (dst->current)
1123     dst->indx = dst->current->indx;
1124
1125   return changed;
1126 }
1127
1128 /* A &= ~B. Returns true if A changes */
1129
1130 bool
1131 bitmap_and_compl_into (bitmap a, const_bitmap b)
1132 {
1133   bitmap_element *a_elt = a->first;
1134   const bitmap_element *b_elt = b->first;
1135   bitmap_element *next;
1136   BITMAP_WORD changed = 0;
1137
1138   if (a == b)
1139     {
1140       if (bitmap_empty_p (a))
1141         return false;
1142       else
1143         {
1144           bitmap_clear (a);
1145           return true;
1146         }
1147     }
1148
1149   while (a_elt && b_elt)
1150     {
1151       if (a_elt->indx < b_elt->indx)
1152         a_elt = a_elt->next;
1153       else if (b_elt->indx < a_elt->indx)
1154         b_elt = b_elt->next;
1155       else
1156         {
1157           /* Matching elts, generate A &= ~B.  */
1158           unsigned ix;
1159           BITMAP_WORD ior = 0;
1160
1161           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1162             {
1163               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1164               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1165
1166               a_elt->bits[ix] = r;
1167               changed |= cleared;
1168               ior |= r;
1169             }
1170           next = a_elt->next;
1171           if (!ior)
1172             bitmap_element_free (a, a_elt);
1173           a_elt = next;
1174           b_elt = b_elt->next;
1175         }
1176     }
1177   gcc_checking_assert (!a->current == !a->first
1178                        && (!a->current || a->indx == a->current->indx));
1179   return changed != 0;
1180 }
1181
1182 /* Set COUNT bits from START in HEAD.  */
1183 void
1184 bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1185 {
1186   unsigned int first_index, end_bit_plus1, last_index;
1187   bitmap_element *elt, *elt_prev;
1188   unsigned int i;
1189
1190   if (!count)
1191     return;
1192
1193   first_index = start / BITMAP_ELEMENT_ALL_BITS;
1194   end_bit_plus1 = start + count;
1195   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1196   elt = bitmap_find_bit (head, start);
1197
1198   /* If bitmap_find_bit returns zero, the current is the closest block
1199      to the result.  Otherwise, just use bitmap_element_allocate to
1200      ensure ELT is set; in the loop below, ELT == NULL means "insert
1201      at the end of the bitmap".  */
1202   if (!elt)
1203     {
1204       elt = bitmap_element_allocate (head);
1205       elt->indx = first_index;
1206       bitmap_element_link (head, elt);
1207     }
1208
1209   gcc_checking_assert (elt->indx == first_index);
1210   elt_prev = elt->prev;
1211   for (i = first_index; i <= last_index; i++)
1212     {
1213       unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1214       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1215
1216       unsigned int first_word_to_mod;
1217       BITMAP_WORD first_mask;
1218       unsigned int last_word_to_mod;
1219       BITMAP_WORD last_mask;
1220       unsigned int ix;
1221
1222       if (!elt || elt->indx != i)
1223         elt = bitmap_elt_insert_after (head, elt_prev, i);
1224
1225       if (elt_start_bit <= start)
1226         {
1227           /* The first bit to turn on is somewhere inside this
1228              elt.  */
1229           first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1230
1231           /* This mask should have 1s in all bits >= start position. */
1232           first_mask =
1233             (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1234           first_mask = ~first_mask;
1235         }
1236       else
1237         {
1238           /* The first bit to turn on is below this start of this elt.  */
1239           first_word_to_mod = 0;
1240           first_mask = ~(BITMAP_WORD) 0;
1241         }
1242
1243       if (elt_end_bit_plus1 <= end_bit_plus1)
1244         {
1245           /* The last bit to turn on is beyond this elt.  */
1246           last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1247           last_mask = ~(BITMAP_WORD) 0;
1248         }
1249       else
1250         {
1251           /* The last bit to turn on is inside to this elt.  */
1252           last_word_to_mod =
1253             (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1254
1255           /* The last mask should have 1s below the end bit.  */
1256           last_mask =
1257             (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1258         }
1259
1260       if (first_word_to_mod == last_word_to_mod)
1261         {
1262           BITMAP_WORD mask = first_mask & last_mask;
1263           elt->bits[first_word_to_mod] |= mask;
1264         }
1265       else
1266         {
1267           elt->bits[first_word_to_mod] |= first_mask;
1268           if (BITMAP_ELEMENT_WORDS > 2)
1269             for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1270               elt->bits[ix] = ~(BITMAP_WORD) 0;
1271           elt->bits[last_word_to_mod] |= last_mask;
1272         }
1273
1274       elt_prev = elt;
1275       elt = elt->next;
1276     }
1277
1278   head->current = elt ? elt : elt_prev;
1279   head->indx = head->current->indx;
1280 }
1281
1282 /* Clear COUNT bits from START in HEAD.  */
1283 void
1284 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1285 {
1286   unsigned int first_index, end_bit_plus1, last_index;
1287   bitmap_element *elt;
1288
1289   if (!count)
1290     return;
1291
1292   first_index = start / BITMAP_ELEMENT_ALL_BITS;
1293   end_bit_plus1 = start + count;
1294   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1295   elt = bitmap_find_bit (head, start);
1296
1297   /* If bitmap_find_bit returns zero, the current is the closest block
1298      to the result.  If the current is less than first index, find the
1299      next one.  Otherwise, just set elt to be current.  */
1300   if (!elt)
1301     {
1302       if (head->current)
1303         {
1304           if (head->indx < first_index)
1305             {
1306               elt = head->current->next;
1307               if (!elt)
1308                 return;
1309             }
1310           else
1311             elt = head->current;
1312         }
1313       else
1314         return;
1315     }
1316
1317   while (elt && (elt->indx <= last_index))
1318     {
1319       bitmap_element * next_elt = elt->next;
1320       unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1321       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1322
1323
1324       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1325         /* Get rid of the entire elt and go to the next one.  */
1326         bitmap_element_free (head, elt);
1327       else
1328         {
1329           /* Going to have to knock out some bits in this elt.  */
1330           unsigned int first_word_to_mod;
1331           BITMAP_WORD first_mask;
1332           unsigned int last_word_to_mod;
1333           BITMAP_WORD last_mask;
1334           unsigned int i;
1335           bool clear = true;
1336
1337           if (elt_start_bit <= start)
1338             {
1339               /* The first bit to turn off is somewhere inside this
1340                  elt.  */
1341               first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1342
1343               /* This mask should have 1s in all bits >= start position. */
1344               first_mask =
1345                 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1346               first_mask = ~first_mask;
1347             }
1348           else
1349             {
1350               /* The first bit to turn off is below this start of this elt.  */
1351               first_word_to_mod = 0;
1352               first_mask = 0;
1353               first_mask = ~first_mask;
1354             }
1355
1356           if (elt_end_bit_plus1 <= end_bit_plus1)
1357             {
1358               /* The last bit to turn off is beyond this elt.  */
1359               last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1360               last_mask = 0;
1361               last_mask = ~last_mask;
1362             }
1363           else
1364             {
1365               /* The last bit to turn off is inside to this elt.  */
1366               last_word_to_mod =
1367                 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1368
1369               /* The last mask should have 1s below the end bit.  */
1370               last_mask =
1371                 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1372             }
1373
1374
1375           if (first_word_to_mod == last_word_to_mod)
1376             {
1377               BITMAP_WORD mask = first_mask & last_mask;
1378               elt->bits[first_word_to_mod] &= ~mask;
1379             }
1380           else
1381             {
1382               elt->bits[first_word_to_mod] &= ~first_mask;
1383               if (BITMAP_ELEMENT_WORDS > 2)
1384                 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1385                   elt->bits[i] = 0;
1386               elt->bits[last_word_to_mod] &= ~last_mask;
1387             }
1388           for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1389             if (elt->bits[i])
1390               {
1391                 clear = false;
1392                 break;
1393               }
1394           /* Check to see if there are any bits left.  */
1395           if (clear)
1396             bitmap_element_free (head, elt);
1397         }
1398       elt = next_elt;
1399     }
1400
1401   if (elt)
1402     {
1403       head->current = elt;
1404       head->indx = head->current->indx;
1405     }
1406 }
1407
1408 /* A = ~A & B. */
1409
1410 void
1411 bitmap_compl_and_into (bitmap a, const_bitmap b)
1412 {
1413   bitmap_element *a_elt = a->first;
1414   const bitmap_element *b_elt = b->first;
1415   bitmap_element *a_prev = NULL;
1416   bitmap_element *next;
1417
1418   gcc_assert (a != b);
1419
1420   if (bitmap_empty_p (a))
1421     {
1422       bitmap_copy (a, b);
1423       return;
1424     }
1425   if (bitmap_empty_p (b))
1426     {
1427       bitmap_clear (a);
1428       return;
1429     }
1430
1431   while (a_elt || b_elt)
1432     {
1433       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1434         {
1435           /* A is before B.  Remove A */
1436           next = a_elt->next;
1437           a_prev = a_elt->prev;
1438           bitmap_element_free (a, a_elt);
1439           a_elt = next;
1440         }
1441       else if (!a_elt || b_elt->indx < a_elt->indx)
1442         {
1443           /* B is before A.  Copy B. */
1444           next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1445           memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1446           a_prev = next;
1447           b_elt = b_elt->next;
1448         }
1449       else
1450         {
1451           /* Matching elts, generate A = ~A & B.  */
1452           unsigned ix;
1453           BITMAP_WORD ior = 0;
1454
1455           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1456             {
1457               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1458               BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1459
1460               a_elt->bits[ix] = r;
1461               ior |= r;
1462             }
1463           next = a_elt->next;
1464           if (!ior)
1465             bitmap_element_free (a, a_elt);
1466           else
1467             a_prev = a_elt;
1468           a_elt = next;
1469           b_elt = b_elt->next;
1470         }
1471     }
1472   gcc_checking_assert (!a->current == !a->first
1473                        && (!a->current || a->indx == a->current->indx));
1474   return;
1475 }
1476
1477
1478 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1479    overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
1480    had already been changed; the new value of CHANGED is returned.  */
1481
1482 static inline bool
1483 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1484                 const bitmap_element *a_elt, const bitmap_element *b_elt,
1485                 bool changed)
1486 {
1487   gcc_assert (a_elt || b_elt);
1488
1489   if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1490     {
1491       /* Matching elts, generate A | B.  */
1492       unsigned ix;
1493
1494       if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1495         {
1496           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1497             {
1498               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1499               if (r != dst_elt->bits[ix])
1500                 {
1501                   dst_elt->bits[ix] = r;
1502                   changed = true;
1503                 }
1504             }
1505         }
1506       else
1507         {
1508           changed = true;
1509           if (!dst_elt)
1510             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1511           else
1512             dst_elt->indx = a_elt->indx;
1513           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1514             {
1515               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1516               dst_elt->bits[ix] = r;
1517             }
1518         }
1519     }
1520   else
1521     {
1522       /* Copy a single element.  */
1523       const bitmap_element *src;
1524
1525       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1526         src = a_elt;
1527       else
1528         src = b_elt;
1529
1530       gcc_checking_assert (src);
1531       changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1532     }
1533   return changed;
1534 }
1535
1536
1537 /* DST = A | B.  Return true if DST changes.  */
1538
1539 bool
1540 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1541 {
1542   bitmap_element *dst_elt = dst->first;
1543   const bitmap_element *a_elt = a->first;
1544   const bitmap_element *b_elt = b->first;
1545   bitmap_element *dst_prev = NULL;
1546   bitmap_element **dst_prev_pnext = &dst->first;
1547   bool changed = false;
1548
1549   gcc_assert (dst != a && dst != b);
1550
1551   while (a_elt || b_elt)
1552     {
1553       changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1554
1555       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1556         {
1557           a_elt = a_elt->next;
1558           b_elt = b_elt->next;
1559         }
1560       else
1561         {
1562           if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1563             a_elt = a_elt->next;
1564           else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1565             b_elt = b_elt->next;
1566         }
1567
1568       dst_prev = *dst_prev_pnext;
1569       dst_prev_pnext = &dst_prev->next;
1570       dst_elt = *dst_prev_pnext;
1571     }
1572
1573   if (dst_elt)
1574     {
1575       changed = true;
1576       bitmap_elt_clear_from (dst, dst_elt);
1577     }
1578   gcc_checking_assert (!dst->current == !dst->first);
1579   if (dst->current)
1580     dst->indx = dst->current->indx;
1581   return changed;
1582 }
1583
1584 /* A |= B.  Return true if A changes.  */
1585
1586 bool
1587 bitmap_ior_into (bitmap a, const_bitmap b)
1588 {
1589   bitmap_element *a_elt = a->first;
1590   const bitmap_element *b_elt = b->first;
1591   bitmap_element *a_prev = NULL;
1592   bitmap_element **a_prev_pnext = &a->first;
1593   bool changed = false;
1594
1595   if (a == b)
1596     return false;
1597
1598   while (b_elt)
1599     {
1600       /* If A lags behind B, just advance it.  */
1601       if (!a_elt || a_elt->indx == b_elt->indx)
1602         {
1603           changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1604           b_elt = b_elt->next;
1605         }
1606       else if (a_elt->indx > b_elt->indx)
1607         {
1608           changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1609           b_elt = b_elt->next;
1610         }
1611
1612       a_prev = *a_prev_pnext;
1613       a_prev_pnext = &a_prev->next;
1614       a_elt = *a_prev_pnext;
1615     }
1616
1617   gcc_checking_assert (!a->current == !a->first);
1618   if (a->current)
1619     a->indx = a->current->indx;
1620   return changed;
1621 }
1622
1623 /* DST = A ^ B  */
1624
1625 void
1626 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1627 {
1628   bitmap_element *dst_elt = dst->first;
1629   const bitmap_element *a_elt = a->first;
1630   const bitmap_element *b_elt = b->first;
1631   bitmap_element *dst_prev = NULL;
1632
1633   gcc_assert (dst != a && dst != b);
1634   if (a == b)
1635     {
1636       bitmap_clear (dst);
1637       return;
1638     }
1639
1640   while (a_elt || b_elt)
1641     {
1642       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1643         {
1644           /* Matching elts, generate A ^ B.  */
1645           unsigned ix;
1646           BITMAP_WORD ior = 0;
1647
1648           if (!dst_elt)
1649             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1650           else
1651             dst_elt->indx = a_elt->indx;
1652           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1653             {
1654               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1655
1656               ior |= r;
1657               dst_elt->bits[ix] = r;
1658             }
1659           a_elt = a_elt->next;
1660           b_elt = b_elt->next;
1661           if (ior)
1662             {
1663               dst_prev = dst_elt;
1664               dst_elt = dst_elt->next;
1665             }
1666         }
1667       else
1668         {
1669           /* Copy a single element.  */
1670           const bitmap_element *src;
1671
1672           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1673             {
1674               src = a_elt;
1675               a_elt = a_elt->next;
1676             }
1677           else
1678             {
1679               src = b_elt;
1680               b_elt = b_elt->next;
1681             }
1682
1683           if (!dst_elt)
1684             dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1685           else
1686             dst_elt->indx = src->indx;
1687           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1688           dst_prev = dst_elt;
1689           dst_elt = dst_elt->next;
1690         }
1691     }
1692   /* Ensure that dst->current is valid.  */
1693   dst->current = dst->first;
1694   bitmap_elt_clear_from (dst, dst_elt);
1695   gcc_checking_assert (!dst->current == !dst->first);
1696   if (dst->current)
1697     dst->indx = dst->current->indx;
1698 }
1699
1700 /* A ^= B */
1701
1702 void
1703 bitmap_xor_into (bitmap a, const_bitmap b)
1704 {
1705   bitmap_element *a_elt = a->first;
1706   const bitmap_element *b_elt = b->first;
1707   bitmap_element *a_prev = NULL;
1708
1709   if (a == b)
1710     {
1711       bitmap_clear (a);
1712       return;
1713     }
1714
1715   while (b_elt)
1716     {
1717       if (!a_elt || b_elt->indx < a_elt->indx)
1718         {
1719           /* Copy b_elt.  */
1720           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1721           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1722           a_prev = dst;
1723           b_elt = b_elt->next;
1724         }
1725       else if (a_elt->indx < b_elt->indx)
1726         {
1727           a_prev = a_elt;
1728           a_elt = a_elt->next;
1729         }
1730       else
1731         {
1732           /* Matching elts, generate A ^= B.  */
1733           unsigned ix;
1734           BITMAP_WORD ior = 0;
1735           bitmap_element *next = a_elt->next;
1736
1737           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1738             {
1739               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1740
1741               ior |= r;
1742               a_elt->bits[ix] = r;
1743             }
1744           b_elt = b_elt->next;
1745           if (ior)
1746             a_prev = a_elt;
1747           else
1748             bitmap_element_free (a, a_elt);
1749           a_elt = next;
1750         }
1751     }
1752   gcc_checking_assert (!a->current == !a->first);
1753   if (a->current)
1754     a->indx = a->current->indx;
1755 }
1756
1757 /* Return true if two bitmaps are identical.
1758    We do not bother with a check for pointer equality, as that never
1759    occurs in practice.  */
1760
1761 bool
1762 bitmap_equal_p (const_bitmap a, const_bitmap b)
1763 {
1764   const bitmap_element *a_elt;
1765   const bitmap_element *b_elt;
1766   unsigned ix;
1767
1768   for (a_elt = a->first, b_elt = b->first;
1769        a_elt && b_elt;
1770        a_elt = a_elt->next, b_elt = b_elt->next)
1771     {
1772       if (a_elt->indx != b_elt->indx)
1773         return false;
1774       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1775         if (a_elt->bits[ix] != b_elt->bits[ix])
1776           return false;
1777     }
1778   return !a_elt && !b_elt;
1779 }
1780
1781 /* Return true if A AND B is not empty.  */
1782
1783 bool
1784 bitmap_intersect_p (const_bitmap a, const_bitmap b)
1785 {
1786   const bitmap_element *a_elt;
1787   const bitmap_element *b_elt;
1788   unsigned ix;
1789
1790   for (a_elt = a->first, b_elt = b->first;
1791        a_elt && b_elt;)
1792     {
1793       if (a_elt->indx < b_elt->indx)
1794         a_elt = a_elt->next;
1795       else if (b_elt->indx < a_elt->indx)
1796         b_elt = b_elt->next;
1797       else
1798         {
1799           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1800             if (a_elt->bits[ix] & b_elt->bits[ix])
1801               return true;
1802           a_elt = a_elt->next;
1803           b_elt = b_elt->next;
1804         }
1805     }
1806   return false;
1807 }
1808
1809 /* Return true if A AND NOT B is not empty.  */
1810
1811 bool
1812 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1813 {
1814   const bitmap_element *a_elt;
1815   const bitmap_element *b_elt;
1816   unsigned ix;
1817   for (a_elt = a->first, b_elt = b->first;
1818        a_elt && b_elt;)
1819     {
1820       if (a_elt->indx < b_elt->indx)
1821         return true;
1822       else if (b_elt->indx < a_elt->indx)
1823         b_elt = b_elt->next;
1824       else
1825         {
1826           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1827             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1828               return true;
1829           a_elt = a_elt->next;
1830           b_elt = b_elt->next;
1831         }
1832     }
1833   return a_elt != NULL;
1834 }
1835
1836 \f
1837 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1838
1839 bool
1840 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1841 {
1842   bool changed = false;
1843
1844   bitmap_element *dst_elt = dst->first;
1845   const bitmap_element *a_elt = a->first;
1846   const bitmap_element *b_elt = b->first;
1847   const bitmap_element *kill_elt = kill->first;
1848   bitmap_element *dst_prev = NULL;
1849   bitmap_element **dst_prev_pnext = &dst->first;
1850
1851   gcc_assert (dst != a && dst != b && dst != kill);
1852
1853   /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
1854   if (b == kill || bitmap_empty_p (b))
1855     {
1856       changed = !bitmap_equal_p (dst, a);
1857       if (changed)
1858         bitmap_copy (dst, a);
1859       return changed;
1860     }
1861   if (bitmap_empty_p (kill))
1862     return bitmap_ior (dst, a, b);
1863   if (bitmap_empty_p (a))
1864     return bitmap_and_compl (dst, b, kill);
1865
1866   while (a_elt || b_elt)
1867     {
1868       bool new_element = false;
1869
1870       if (b_elt)
1871         while (kill_elt && kill_elt->indx < b_elt->indx)
1872           kill_elt = kill_elt->next;
1873
1874       if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1875           && (!a_elt || a_elt->indx >= b_elt->indx))
1876         {
1877           bitmap_element tmp_elt;
1878           unsigned ix;
1879
1880           BITMAP_WORD ior = 0;
1881           tmp_elt.indx = b_elt->indx;
1882           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1883             {
1884               BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1885               ior |= r;
1886               tmp_elt.bits[ix] = r;
1887             }
1888
1889           if (ior)
1890             {
1891               changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1892                                         a_elt, &tmp_elt, changed);
1893               new_element = true;
1894               if (a_elt && a_elt->indx == b_elt->indx)
1895                 a_elt = a_elt->next;
1896             }
1897
1898           b_elt = b_elt->next;
1899           kill_elt = kill_elt->next;
1900         }
1901       else
1902         {
1903           changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1904                                     a_elt, b_elt, changed);
1905           new_element = true;
1906
1907           if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1908             {
1909               a_elt = a_elt->next;
1910               b_elt = b_elt->next;
1911             }
1912           else
1913             {
1914               if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1915                 a_elt = a_elt->next;
1916               else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1917                 b_elt = b_elt->next;
1918             }
1919         }
1920
1921       if (new_element)
1922         {
1923           dst_prev = *dst_prev_pnext;
1924           dst_prev_pnext = &dst_prev->next;
1925           dst_elt = *dst_prev_pnext;
1926         }
1927     }
1928
1929   if (dst_elt)
1930     {
1931       changed = true;
1932       bitmap_elt_clear_from (dst, dst_elt);
1933     }
1934   gcc_checking_assert (!dst->current == !dst->first);
1935   if (dst->current)
1936     dst->indx = dst->current->indx;
1937
1938   return changed;
1939 }
1940
1941 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1942
1943 bool
1944 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1945 {
1946   bitmap_head tmp;
1947   bool changed;
1948
1949   bitmap_initialize (&tmp, &bitmap_default_obstack);
1950   bitmap_and_compl (&tmp, from1, from2);
1951   changed = bitmap_ior_into (a, &tmp);
1952   bitmap_clear (&tmp);
1953
1954   return changed;
1955 }
1956
1957 /* A |= (B & C).  Return true if A changes.  */
1958
1959 bool
1960 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1961 {
1962   bitmap_element *a_elt = a->first;
1963   const bitmap_element *b_elt = b->first;
1964   const bitmap_element *c_elt = c->first;
1965   bitmap_element and_elt;
1966   bitmap_element *a_prev = NULL;
1967   bitmap_element **a_prev_pnext = &a->first;
1968   bool changed = false;
1969   unsigned ix;
1970
1971   if (b == c)
1972     return bitmap_ior_into (a, b);
1973   if (bitmap_empty_p (b) || bitmap_empty_p (c))
1974     return false;
1975
1976   and_elt.indx = -1;
1977   while (b_elt && c_elt)
1978     {
1979       BITMAP_WORD overall;
1980
1981       /* Find a common item of B and C.  */
1982       while (b_elt->indx != c_elt->indx)
1983         {
1984           if (b_elt->indx < c_elt->indx)
1985             {
1986               b_elt = b_elt->next;
1987               if (!b_elt)
1988                 goto done;
1989             }
1990           else
1991             {
1992               c_elt = c_elt->next;
1993               if (!c_elt)
1994                 goto done;
1995             }
1996         }
1997
1998       overall = 0;
1999       and_elt.indx = b_elt->indx;
2000       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2001         {
2002           and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2003           overall |= and_elt.bits[ix];
2004         }
2005
2006       b_elt = b_elt->next;
2007       c_elt = c_elt->next;
2008       if (!overall)
2009         continue;
2010
2011       /* Now find a place to insert AND_ELT.  */
2012       do
2013         {
2014           ix = a_elt ? a_elt->indx : and_elt.indx;
2015           if (ix == and_elt.indx)
2016             changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2017           else if (ix > and_elt.indx)
2018             changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2019
2020           a_prev = *a_prev_pnext;
2021           a_prev_pnext = &a_prev->next;
2022           a_elt = *a_prev_pnext;
2023
2024           /* If A lagged behind B/C, we advanced it so loop once more.  */
2025         }
2026       while (ix < and_elt.indx);
2027     }
2028
2029  done:
2030   gcc_checking_assert (!a->current == !a->first);
2031   if (a->current)
2032     a->indx = a->current->indx;
2033   return changed;
2034 }
2035 \f
2036 /* Debugging function to print out the contents of a bitmap.  */
2037
2038 DEBUG_FUNCTION void
2039 debug_bitmap_file (FILE *file, const_bitmap head)
2040 {
2041   const bitmap_element *ptr;
2042
2043   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2044            " current = " HOST_PTR_PRINTF " indx = %u\n",
2045            (void *) head->first, (void *) head->current, head->indx);
2046
2047   for (ptr = head->first; ptr; ptr = ptr->next)
2048     {
2049       unsigned int i, j, col = 26;
2050
2051       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2052                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2053                (const void*) ptr, (const void*) ptr->next,
2054                (const void*) ptr->prev, ptr->indx);
2055
2056       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2057         for (j = 0; j < BITMAP_WORD_BITS; j++)
2058           if ((ptr->bits[i] >> j) & 1)
2059             {
2060               if (col > 70)
2061                 {
2062                   fprintf (file, "\n\t\t\t");
2063                   col = 24;
2064                 }
2065
2066               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2067                                      + i * BITMAP_WORD_BITS + j));
2068               col += 4;
2069             }
2070
2071       fprintf (file, " }\n");
2072     }
2073 }
2074
2075 /* Function to be called from the debugger to print the contents
2076    of a bitmap.  */
2077
2078 DEBUG_FUNCTION void
2079 debug_bitmap (const_bitmap head)
2080 {
2081   debug_bitmap_file (stdout, head);
2082 }
2083
2084 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
2085    it does not print anything but the bits.  */
2086
2087 DEBUG_FUNCTION void
2088 bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
2089 {
2090   const char *comma = "";
2091   unsigned i;
2092   bitmap_iterator bi;
2093
2094   fputs (prefix, file);
2095   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2096     {
2097       fprintf (file, "%s%d", comma, i);
2098       comma = ", ";
2099     }
2100   fputs (suffix, file);
2101 }
2102 #ifdef GATHER_STATISTICS
2103
2104
2105 /* Used to accumulate statistics about bitmap sizes.  */
2106 struct output_info
2107 {
2108   HOST_WIDEST_INT size;
2109   int count;
2110 };
2111
2112 /* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
2113    and update statistics.  */
2114 static int
2115 print_statistics (void **slot, void *b)
2116 {
2117   struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
2118   struct output_info *i = (struct output_info *) b;
2119   char s[4096];
2120
2121   if (d->allocated)
2122     {
2123       const char *s1 = d->file;
2124       const char *s2;
2125       while ((s2 = strstr (s1, "gcc/")))
2126         s1 = s2 + 4;
2127       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
2128       s[41] = 0;
2129       fprintf (stderr, "%-41s %8d %15"HOST_WIDEST_INT_PRINT"d %15"
2130                HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d %10d\n",
2131                s, d->created, d->allocated, d->peak, d->current, d->nsearches,
2132                d->search_iter);
2133       i->size += d->allocated;
2134       i->count += d->created;
2135     }
2136   return 1;
2137 }
2138 #endif
2139 /* Output per-bitmap memory usage statistics.  */
2140 void
2141 dump_bitmap_statistics (void)
2142 {
2143 #ifdef GATHER_STATISTICS
2144   struct output_info info;
2145
2146   if (!bitmap_desc_hash)
2147     return;
2148
2149   fprintf (stderr, "\nBitmap                                     Overall "
2150                    "      Allocated            Peak            Leak   searched "
2151                    "  search itr\n");
2152   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2153   info.count = 0;
2154   info.size = 0;
2155   htab_traverse (bitmap_desc_hash, print_statistics, &info);
2156   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2157   fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n",
2158            "Total", info.count, info.size);
2159   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2160 #endif
2161 }
2162
2163 /* Compute hash of bitmap (for purposes of hashing).  */
2164 hashval_t
2165 bitmap_hash (const_bitmap head)
2166 {
2167   const bitmap_element *ptr;
2168   BITMAP_WORD hash = 0;
2169   int ix;
2170
2171   for (ptr = head->first; ptr; ptr = ptr->next)
2172     {
2173       hash ^= ptr->indx;
2174       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2175         hash ^= ptr->bits[ix];
2176     }
2177   return (hashval_t)hash;
2178 }
2179
2180 #include "gt-bitmap.h"