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