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         {
 628           ptr->bits[word_num] &= ~bit_val;
 629           /* If we cleared the entire word, free up the element.  */
 630           if (!ptr->bits[word_num]
 631               && bitmap_element_zerop (ptr))
 632             bitmap_element_free (head, ptr);
 633         }
 634
 635       return res;
 636     }
 637
 638   return false;
 639 }
 640
 641 /* Set a single bit in a bitmap.  Return true if the bit changed.  */
 642
 643 bool
 644 bitmap_set_bit (bitmap head, int bit)
 645 {
 646   bitmap_element *ptr = bitmap_find_bit (head, bit);
 647   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 648   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 649   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 650
 651   if (ptr == 0)
 652     {
 653       ptr = bitmap_element_allocate (head);
 654       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 655       ptr->bits[word_num] = bit_val;
 656       bitmap_element_link (head, ptr);
 657       return true;
 658     }
 659   else
 660     {
 661       bool res = (ptr->bits[word_num] & bit_val) == 0;
 662       if (res)
 663         ptr->bits[word_num] |= bit_val;
 664       return res;
 665     }
 666 }
 667
 668 /* Return whether a bit is set within a bitmap.  */
 669
 670 int
 671 bitmap_bit_p (bitmap head, int bit)
 672 {
 673   bitmap_element *ptr;
 674   unsigned bit_num;
 675   unsigned word_num;
 676
 677   ptr = bitmap_find_bit (head, bit);
 678   if (ptr == 0)
 679     return 0;
 680
 681   bit_num = bit % BITMAP_WORD_BITS;
 682   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 683
 684   return (ptr->bits[word_num] >> bit_num) & 1;
 685 }
 686 \f
 687 #if GCC_VERSION < 3400
 688 /* Table of number of set bits in a character, indexed by value of char.  */
 689 static const unsigned char popcount_table[] =
 690 {
 691     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,
 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     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     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,
 696     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,
 697     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,
 698     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,
 699 };
 700
 701 static unsigned long
 702 bitmap_popcount (BITMAP_WORD a)
 703 {
 704   unsigned long ret = 0;
 705   unsigned i;
 706
 707   /* Just do this the table way for now  */
 708   for (i = 0; i < BITMAP_WORD_BITS; i+= 8)
 709     ret += popcount_table[(a >> i) & 0xff];
 710   return ret;
 711 }
 712 #endif
 713 /* Count the number of bits set in the bitmap, and return it.  */
 714
 715 unsigned long
 716 bitmap_count_bits (const_bitmap a)
 717 {
 718   unsigned long count = 0;
 719   const bitmap_element *elt;
 720   unsigned ix;
 721
 722   for (elt = a->first; elt; elt = elt->next)
 723     {
 724       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 725         {
 726 #if GCC_VERSION >= 3400
 727           /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 728          of BITMAP_WORD is not material.  */
 729           count += __builtin_popcountl (elt->bits[ix]);
 730 #else
 731           count += bitmap_popcount (elt->bits[ix]);
 732 #endif
 733         }
 734     }
 735   return count;
 736 }
 737
 738 /* Return true if the bitmap has a single bit set.  Otherwise return
 739    false.  */
 740
 741 bool
 742 bitmap_single_bit_set_p (const_bitmap a)
 743 {
 744   unsigned long count = 0;
 745   const bitmap_element *elt;
 746   unsigned ix;
 747
 748   if (bitmap_empty_p (a))
 749     return false;
 750
 751   elt = a->first;
 752   /* As there are no completely empty bitmap elements, a second one
 753      means we have more than one bit set.  */
 754   if (elt->next != NULL)
 755     return false;
 756
 757   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 758     {
 759 #if GCC_VERSION >= 3400
 760       /* Note that popcountl matches BITMAP_WORD in type, so the actual size
 761          of BITMAP_WORD is not material.  */
 762       count += __builtin_popcountl (elt->bits[ix]);
 763 #else
 764       count += bitmap_popcount (elt->bits[ix]);
 765 #endif
 766       if (count > 1)
 767         return false;
 768     }
 769
 770   return count == 1;
 771 }
 772
 773
 774 /* Return the bit number of the first set bit in the bitmap.  The
 775    bitmap must be non-empty.  */
 776
 777 unsigned
 778 bitmap_first_set_bit (const_bitmap a)
 779 {
 780   const bitmap_element *elt = a->first;
 781   unsigned bit_no;
 782   BITMAP_WORD word;
 783   unsigned ix;
 784
 785   gcc_checking_assert (elt);
 786   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 787   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 788     {
 789       word = elt->bits[ix];
 790       if (word)
 791         goto found_bit;
 792     }
 793   gcc_unreachable ();
 794  found_bit:
 795   bit_no += ix * BITMAP_WORD_BITS;
 796
 797 #if GCC_VERSION >= 3004
 798   gcc_assert (sizeof(long) == sizeof (word));
 799   bit_no += __builtin_ctzl (word);
 800 #else
 801   /* Binary search for the first set bit.  */
 802 #if BITMAP_WORD_BITS > 64
 803 #error "Fill out the table."
 804 #endif
 805 #if BITMAP_WORD_BITS > 32
 806   if (!(word & 0xffffffff))
 807     word >>= 32, bit_no += 32;
 808 #endif
 809   if (!(word & 0xffff))
 810     word >>= 16, bit_no += 16;
 811   if (!(word & 0xff))
 812     word >>= 8, bit_no += 8;
 813   if (!(word & 0xf))
 814     word >>= 4, bit_no += 4;
 815   if (!(word & 0x3))
 816     word >>= 2, bit_no += 2;
 817   if (!(word & 0x1))
 818     word >>= 1, bit_no += 1;
 819
 820  gcc_checking_assert (word & 1);
 821 #endif
 822  return bit_no;
 823 }
 824
 825 /* Return the bit number of the first set bit in the bitmap.  The
 826    bitmap must be non-empty.  */
 827
 828 unsigned
 829 bitmap_last_set_bit (const_bitmap a)
 830 {
 831   const bitmap_element *elt = a->current ? a->current : a->first;
 832   unsigned bit_no;
 833   BITMAP_WORD word;
 834   int ix;
 835
 836   gcc_checking_assert (elt);
 837   while (elt->next)
 838     elt = elt->next;
 839   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 840   for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--)
 841     {
 842       word = elt->bits[ix];
 843       if (word)
 844         goto found_bit;
 845     }
 846   gcc_unreachable ();
 847  found_bit:
 848   bit_no += ix * BITMAP_WORD_BITS;
 849
 850   /* Binary search for the last set bit.  */
 851 #if GCC_VERSION >= 3004
 852   gcc_assert (sizeof(long) == sizeof (word));
 853   bit_no += sizeof (long) * 8 - __builtin_ctzl (word);
 854 #else
 855 #if BITMAP_WORD_BITS > 64
 856 #error "Fill out the table."
 857 #endif
 858 #if BITMAP_WORD_BITS > 32
 859   if ((word & 0xffffffff00000000))
 860     word >>= 32, bit_no += 32;
 861 #endif
 862   if (word & 0xffff0000)
 863     word >>= 16, bit_no += 16;
 864   if (!(word & 0xff00))
 865     word >>= 8, bit_no += 8;
 866   if (!(word & 0xf0))
 867     word >>= 4, bit_no += 4;
 868   if (!(word & 12))
 869     word >>= 2, bit_no += 2;
 870   if (!(word & 2))
 871     word >>= 1, bit_no += 1;
 872 #endif
 873
 874  gcc_checking_assert (word & 1);
 875  return bit_no;
 876 }
 877 \f
 878
 879 /* DST = A & B.  */
 880
 881 void
 882 bitmap_and (bitmap dst, const_bitmap a, const_bitmap b)
 883 {
 884   bitmap_element *dst_elt = dst->first;
 885   const bitmap_element *a_elt = a->first;
 886   const bitmap_element *b_elt = b->first;
 887   bitmap_element *dst_prev = NULL;
 888
 889   gcc_assert (dst != a && dst != b);
 890
 891   if (a == b)
 892     {
 893       bitmap_copy (dst, a);
 894       return;
 895     }
 896
 897   while (a_elt && b_elt)
 898     {
 899       if (a_elt->indx < b_elt->indx)
 900         a_elt = a_elt->next;
 901       else if (b_elt->indx < a_elt->indx)
 902         b_elt = b_elt->next;
 903       else
 904         {
 905           /* Matching elts, generate A & B.  */
 906           unsigned ix;
 907           BITMAP_WORD ior = 0;
 908
 909           if (!dst_elt)
 910             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 911           else
 912             dst_elt->indx = a_elt->indx;
 913           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 914             {
 915               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 916
 917               dst_elt->bits[ix] = r;
 918               ior |= r;
 919             }
 920           if (ior)
 921             {
 922               dst_prev = dst_elt;
 923               dst_elt = dst_elt->next;
 924             }
 925           a_elt = a_elt->next;
 926           b_elt = b_elt->next;
 927         }
 928     }
 929   /* Ensure that dst->current is valid.  */
 930   dst->current = dst->first;
 931   bitmap_elt_clear_from (dst, dst_elt);
 932   gcc_checking_assert (!dst->current == !dst->first);
 933   if (dst->current)
 934     dst->indx = dst->current->indx;
 935 }
 936
 937 /* A &= B.  */
 938
 939 void
 940 bitmap_and_into (bitmap a, const_bitmap b)
 941 {
 942   bitmap_element *a_elt = a->first;
 943   const bitmap_element *b_elt = b->first;
 944   bitmap_element *next;
 945
 946   if (a == b)
 947     return;
 948
 949   while (a_elt && b_elt)
 950     {
 951       if (a_elt->indx < b_elt->indx)
 952         {
 953           next = a_elt->next;
 954           bitmap_element_free (a, a_elt);
 955           a_elt = next;
 956         }
 957       else if (b_elt->indx < a_elt->indx)
 958         b_elt = b_elt->next;
 959       else
 960         {
 961           /* Matching elts, generate A &= B.  */
 962           unsigned ix;
 963           BITMAP_WORD ior = 0;
 964
 965           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 966             {
 967               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 968
 969               a_elt->bits[ix] = r;
 970               ior |= r;
 971             }
 972           next = a_elt->next;
 973           if (!ior)
 974             bitmap_element_free (a, a_elt);
 975           a_elt = next;
 976           b_elt = b_elt->next;
 977         }
 978     }
 979   bitmap_elt_clear_from (a, a_elt);
 980   gcc_checking_assert (!a->current == !a->first
 981                        && (!a->current || a->indx == a->current->indx));
 982 }
 983
 984
 985 /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
 986    if non-NULL.  CHANGED is true if the destination bitmap had already been
 987    changed; the new value of CHANGED is returned.  */
 988
 989 static inline bool
 990 bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
 991                  const bitmap_element *src_elt, bool changed)
 992 {
 993   if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
 994     {
 995       unsigned ix;
 996
 997       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
 998         if (src_elt->bits[ix] != dst_elt->bits[ix])
 999           {
1000             dst_elt->bits[ix] = src_elt->bits[ix];
1001             changed = true;
1002           }
1003     }
1004   else
1005     {
1006       changed = true;
1007       if (!dst_elt)
1008         dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
1009       else
1010         dst_elt->indx = src_elt->indx;
1011       memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
1012     }
1013   return changed;
1014 }
1015
1016
1017
1018 /* DST = A & ~B  */
1019
1020 bool
1021 bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b)
1022 {
1023   bitmap_element *dst_elt = dst->first;
1024   const bitmap_element *a_elt = a->first;
1025   const bitmap_element *b_elt = b->first;
1026   bitmap_element *dst_prev = NULL;
1027   bitmap_element **dst_prev_pnext = &dst->first;
1028   bool changed = false;
1029
1030   gcc_assert (dst != a && dst != b);
1031
1032   if (a == b)
1033     {
1034       changed = !bitmap_empty_p (dst);
1035       bitmap_clear (dst);
1036       return changed;
1037     }
1038
1039   while (a_elt)
1040     {
1041       while (b_elt && b_elt->indx < a_elt->indx)
1042         b_elt = b_elt->next;
1043
1044       if (!b_elt || b_elt->indx > a_elt->indx)
1045         {
1046           changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
1047           dst_prev = *dst_prev_pnext;
1048           dst_prev_pnext = &dst_prev->next;
1049           dst_elt = *dst_prev_pnext;
1050           a_elt = a_elt->next;
1051         }
1052
1053       else
1054         {
1055           /* Matching elts, generate A & ~B.  */
1056           unsigned ix;
1057           BITMAP_WORD ior = 0;
1058
1059           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1060             {
1061               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1062                 {
1063                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1064
1065                   if (dst_elt->bits[ix] != r)
1066                     {
1067                       changed = true;
1068                       dst_elt->bits[ix] = r;
1069                     }
1070                   ior |= r;
1071                 }
1072             }
1073           else
1074             {
1075               bool new_element;
1076               if (!dst_elt || dst_elt->indx > a_elt->indx)
1077                 {
1078                   dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1079                   new_element = true;
1080                 }
1081               else
1082                 {
1083                   dst_elt->indx = a_elt->indx;
1084                   new_element = false;
1085                 }
1086
1087               for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1088                 {
1089                   BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
1090
1091                   dst_elt->bits[ix] = r;
1092                   ior |= r;
1093                 }
1094
1095               if (ior)
1096                 changed = true;
1097               else
1098                 {
1099                   changed |= !new_element;
1100                   bitmap_element_free (dst, dst_elt);
1101                   dst_elt = *dst_prev_pnext;
1102                 }
1103             }
1104
1105           if (ior)
1106             {
1107               dst_prev = *dst_prev_pnext;
1108               dst_prev_pnext = &dst_prev->next;
1109               dst_elt = *dst_prev_pnext;
1110             }
1111           a_elt = a_elt->next;
1112           b_elt = b_elt->next;
1113         }
1114     }
1115
1116   /* Ensure that dst->current is valid.  */
1117   dst->current = dst->first;
1118
1119   if (dst_elt)
1120     {
1121       changed = true;
1122       bitmap_elt_clear_from (dst, dst_elt);
1123     }
1124   gcc_checking_assert (!dst->current == !dst->first);
1125   if (dst->current)
1126     dst->indx = dst->current->indx;
1127
1128   return changed;
1129 }
1130
1131 /* A &= ~B. Returns true if A changes */
1132
1133 bool
1134 bitmap_and_compl_into (bitmap a, const_bitmap b)
1135 {
1136   bitmap_element *a_elt = a->first;
1137   const bitmap_element *b_elt = b->first;
1138   bitmap_element *next;
1139   BITMAP_WORD changed = 0;
1140
1141   if (a == b)
1142     {
1143       if (bitmap_empty_p (a))
1144         return false;
1145       else
1146         {
1147           bitmap_clear (a);
1148           return true;
1149         }
1150     }
1151
1152   while (a_elt && b_elt)
1153     {
1154       if (a_elt->indx < b_elt->indx)
1155         a_elt = a_elt->next;
1156       else if (b_elt->indx < a_elt->indx)
1157         b_elt = b_elt->next;
1158       else
1159         {
1160           /* Matching elts, generate A &= ~B.  */
1161           unsigned ix;
1162           BITMAP_WORD ior = 0;
1163
1164           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1165             {
1166               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1167               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
1168
1169               a_elt->bits[ix] = r;
1170               changed |= cleared;
1171               ior |= r;
1172             }
1173           next = a_elt->next;
1174           if (!ior)
1175             bitmap_element_free (a, a_elt);
1176           a_elt = next;
1177           b_elt = b_elt->next;
1178         }
1179     }
1180   gcc_checking_assert (!a->current == !a->first
1181                        && (!a->current || a->indx == a->current->indx));
1182   return changed != 0;
1183 }
1184
1185 /* Set COUNT bits from START in HEAD.  */
1186 void
1187 bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
1188 {
1189   unsigned int first_index, end_bit_plus1, last_index;
1190   bitmap_element *elt, *elt_prev;
1191   unsigned int i;
1192
1193   if (!count)
1194     return;
1195
1196   first_index = start / BITMAP_ELEMENT_ALL_BITS;
1197   end_bit_plus1 = start + count;
1198   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1199   elt = bitmap_find_bit (head, start);
1200
1201   /* If bitmap_find_bit returns zero, the current is the closest block
1202      to the result.  Otherwise, just use bitmap_element_allocate to
1203      ensure ELT is set; in the loop below, ELT == NULL means "insert
1204      at the end of the bitmap".  */
1205   if (!elt)
1206     {
1207       elt = bitmap_element_allocate (head);
1208       elt->indx = first_index;
1209       bitmap_element_link (head, elt);
1210     }
1211
1212   gcc_checking_assert (elt->indx == first_index);
1213   elt_prev = elt->prev;
1214   for (i = first_index; i <= last_index; i++)
1215     {
1216       unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
1217       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1218
1219       unsigned int first_word_to_mod;
1220       BITMAP_WORD first_mask;
1221       unsigned int last_word_to_mod;
1222       BITMAP_WORD last_mask;
1223       unsigned int ix;
1224
1225       if (!elt || elt->indx != i)
1226         elt = bitmap_elt_insert_after (head, elt_prev, i);
1227
1228       if (elt_start_bit <= start)
1229         {
1230           /* The first bit to turn on is somewhere inside this
1231              elt.  */
1232           first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1233
1234           /* This mask should have 1s in all bits >= start position. */
1235           first_mask =
1236             (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1237           first_mask = ~first_mask;
1238         }
1239       else
1240         {
1241           /* The first bit to turn on is below this start of this elt.  */
1242           first_word_to_mod = 0;
1243           first_mask = ~(BITMAP_WORD) 0;
1244         }
1245
1246       if (elt_end_bit_plus1 <= end_bit_plus1)
1247         {
1248           /* The last bit to turn on is beyond this elt.  */
1249           last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1250           last_mask = ~(BITMAP_WORD) 0;
1251         }
1252       else
1253         {
1254           /* The last bit to turn on is inside to this elt.  */
1255           last_word_to_mod =
1256             (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1257
1258           /* The last mask should have 1s below the end bit.  */
1259           last_mask =
1260             (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
1261         }
1262
1263       if (first_word_to_mod == last_word_to_mod)
1264         {
1265           BITMAP_WORD mask = first_mask & last_mask;
1266           elt->bits[first_word_to_mod] |= mask;
1267         }
1268       else
1269         {
1270           elt->bits[first_word_to_mod] |= first_mask;
1271           if (BITMAP_ELEMENT_WORDS > 2)
1272             for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
1273               elt->bits[ix] = ~(BITMAP_WORD) 0;
1274           elt->bits[last_word_to_mod] |= last_mask;
1275         }
1276
1277       elt_prev = elt;
1278       elt = elt->next;
1279     }
1280
1281   head->current = elt ? elt : elt_prev;
1282   head->indx = head->current->indx;
1283 }
1284
1285 /* Clear COUNT bits from START in HEAD.  */
1286 void
1287 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
1288 {
1289   unsigned int first_index, end_bit_plus1, last_index;
1290   bitmap_element *elt;
1291
1292   if (!count)
1293     return;
1294
1295   first_index = start / BITMAP_ELEMENT_ALL_BITS;
1296   end_bit_plus1 = start + count;
1297   last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
1298   elt = bitmap_find_bit (head, start);
1299
1300   /* If bitmap_find_bit returns zero, the current is the closest block
1301      to the result.  If the current is less than first index, find the
1302      next one.  Otherwise, just set elt to be current.  */
1303   if (!elt)
1304     {
1305       if (head->current)
1306         {
1307           if (head->indx < first_index)
1308             {
1309               elt = head->current->next;
1310               if (!elt)
1311                 return;
1312             }
1313           else
1314             elt = head->current;
1315         }
1316       else
1317         return;
1318     }
1319
1320   while (elt && (elt->indx <= last_index))
1321     {
1322       bitmap_element * next_elt = elt->next;
1323       unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1324       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1325
1326
1327       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1328         /* Get rid of the entire elt and go to the next one.  */
1329         bitmap_element_free (head, elt);
1330       else
1331         {
1332           /* Going to have to knock out some bits in this elt.  */
1333           unsigned int first_word_to_mod;
1334           BITMAP_WORD first_mask;
1335           unsigned int last_word_to_mod;
1336           BITMAP_WORD last_mask;
1337           unsigned int i;
1338           bool clear = true;
1339
1340           if (elt_start_bit <= start)
1341             {
1342               /* The first bit to turn off is somewhere inside this
1343                  elt.  */
1344               first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1345
1346               /* This mask should have 1s in all bits >= start position. */
1347               first_mask =
1348                 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1349               first_mask = ~first_mask;
1350             }
1351           else
1352             {
1353               /* The first bit to turn off is below this start of this elt.  */
1354               first_word_to_mod = 0;
1355               first_mask = 0;
1356               first_mask = ~first_mask;
1357             }
1358
1359           if (elt_end_bit_plus1 <= end_bit_plus1)
1360             {
1361               /* The last bit to turn off is beyond this elt.  */
1362               last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1363               last_mask = 0;
1364               last_mask = ~last_mask;
1365             }
1366           else
1367             {
1368               /* The last bit to turn off is inside to this elt.  */
1369               last_word_to_mod =
1370                 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1371
1372               /* The last mask should have 1s below the end bit.  */
1373               last_mask =
1374                 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1375             }
1376
1377
1378           if (first_word_to_mod == last_word_to_mod)
1379             {
1380               BITMAP_WORD mask = first_mask & last_mask;
1381               elt->bits[first_word_to_mod] &= ~mask;
1382             }
1383           else
1384             {
1385               elt->bits[first_word_to_mod] &= ~first_mask;
1386               if (BITMAP_ELEMENT_WORDS > 2)
1387                 for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1388                   elt->bits[i] = 0;
1389               elt->bits[last_word_to_mod] &= ~last_mask;
1390             }
1391           for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1392             if (elt->bits[i])
1393               {
1394                 clear = false;
1395                 break;
1396               }
1397           /* Check to see if there are any bits left.  */
1398           if (clear)
1399             bitmap_element_free (head, elt);
1400         }
1401       elt = next_elt;
1402     }
1403
1404   if (elt)
1405     {
1406       head->current = elt;
1407       head->indx = head->current->indx;
1408     }
1409 }
1410
1411 /* A = ~A & B. */
1412
1413 void
1414 bitmap_compl_and_into (bitmap a, const_bitmap b)
1415 {
1416   bitmap_element *a_elt = a->first;
1417   const bitmap_element *b_elt = b->first;
1418   bitmap_element *a_prev = NULL;
1419   bitmap_element *next;
1420
1421   gcc_assert (a != b);
1422
1423   if (bitmap_empty_p (a))
1424     {
1425       bitmap_copy (a, b);
1426       return;
1427     }
1428   if (bitmap_empty_p (b))
1429     {
1430       bitmap_clear (a);
1431       return;
1432     }
1433
1434   while (a_elt || b_elt)
1435     {
1436       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1437         {
1438           /* A is before B.  Remove A */
1439           next = a_elt->next;
1440           a_prev = a_elt->prev;
1441           bitmap_element_free (a, a_elt);
1442           a_elt = next;
1443         }
1444       else if (!a_elt || b_elt->indx < a_elt->indx)
1445         {
1446           /* B is before A.  Copy B. */
1447           next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1448           memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1449           a_prev = next;
1450           b_elt = b_elt->next;
1451         }
1452       else
1453         {
1454           /* Matching elts, generate A = ~A & B.  */
1455           unsigned ix;
1456           BITMAP_WORD ior = 0;
1457
1458           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1459             {
1460               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1461               BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1462
1463               a_elt->bits[ix] = r;
1464               ior |= r;
1465             }
1466           next = a_elt->next;
1467           if (!ior)
1468             bitmap_element_free (a, a_elt);
1469           else
1470             a_prev = a_elt;
1471           a_elt = next;
1472           b_elt = b_elt->next;
1473         }
1474     }
1475   gcc_checking_assert (!a->current == !a->first
1476                        && (!a->current || a->indx == a->current->indx));
1477   return;
1478 }
1479
1480
1481 /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
1482    overwriting DST_ELT if non-NULL.  CHANGED is true if the destination bitmap
1483    had already been changed; the new value of CHANGED is returned.  */
1484
1485 static inline bool
1486 bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
1487                 const bitmap_element *a_elt, const bitmap_element *b_elt,
1488                 bool changed)
1489 {
1490   gcc_assert (a_elt || b_elt);
1491
1492   if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1493     {
1494       /* Matching elts, generate A | B.  */
1495       unsigned ix;
1496
1497       if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1498         {
1499           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1500             {
1501               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1502               if (r != dst_elt->bits[ix])
1503                 {
1504                   dst_elt->bits[ix] = r;
1505                   changed = true;
1506                 }
1507             }
1508         }
1509       else
1510         {
1511           changed = true;
1512           if (!dst_elt)
1513             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1514           else
1515             dst_elt->indx = a_elt->indx;
1516           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1517             {
1518               BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1519               dst_elt->bits[ix] = r;
1520             }
1521         }
1522     }
1523   else
1524     {
1525       /* Copy a single element.  */
1526       const bitmap_element *src;
1527
1528       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1529         src = a_elt;
1530       else
1531         src = b_elt;
1532
1533       gcc_checking_assert (src);
1534       changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
1535     }
1536   return changed;
1537 }
1538
1539
1540 /* DST = A | B.  Return true if DST changes.  */
1541
1542 bool
1543 bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
1544 {
1545   bitmap_element *dst_elt = dst->first;
1546   const bitmap_element *a_elt = a->first;
1547   const bitmap_element *b_elt = b->first;
1548   bitmap_element *dst_prev = NULL;
1549   bitmap_element **dst_prev_pnext = &dst->first;
1550   bool changed = false;
1551
1552   gcc_assert (dst != a && dst != b);
1553
1554   while (a_elt || b_elt)
1555     {
1556       changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
1557
1558       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1559         {
1560           a_elt = a_elt->next;
1561           b_elt = b_elt->next;
1562         }
1563       else
1564         {
1565           if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1566             a_elt = a_elt->next;
1567           else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1568             b_elt = b_elt->next;
1569         }
1570
1571       dst_prev = *dst_prev_pnext;
1572       dst_prev_pnext = &dst_prev->next;
1573       dst_elt = *dst_prev_pnext;
1574     }
1575
1576   if (dst_elt)
1577     {
1578       changed = true;
1579       bitmap_elt_clear_from (dst, dst_elt);
1580     }
1581   gcc_checking_assert (!dst->current == !dst->first);
1582   if (dst->current)
1583     dst->indx = dst->current->indx;
1584   return changed;
1585 }
1586
1587 /* A |= B.  Return true if A changes.  */
1588
1589 bool
1590 bitmap_ior_into (bitmap a, const_bitmap b)
1591 {
1592   bitmap_element *a_elt = a->first;
1593   const bitmap_element *b_elt = b->first;
1594   bitmap_element *a_prev = NULL;
1595   bitmap_element **a_prev_pnext = &a->first;
1596   bool changed = false;
1597
1598   if (a == b)
1599     return false;
1600
1601   while (b_elt)
1602     {
1603       /* If A lags behind B, just advance it.  */
1604       if (!a_elt || a_elt->indx == b_elt->indx)
1605         {
1606           changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
1607           b_elt = b_elt->next;
1608         }
1609       else if (a_elt->indx > b_elt->indx)
1610         {
1611           changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
1612           b_elt = b_elt->next;
1613         }
1614
1615       a_prev = *a_prev_pnext;
1616       a_prev_pnext = &a_prev->next;
1617       a_elt = *a_prev_pnext;
1618     }
1619
1620   gcc_checking_assert (!a->current == !a->first);
1621   if (a->current)
1622     a->indx = a->current->indx;
1623   return changed;
1624 }
1625
1626 /* DST = A ^ B  */
1627
1628 void
1629 bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b)
1630 {
1631   bitmap_element *dst_elt = dst->first;
1632   const bitmap_element *a_elt = a->first;
1633   const bitmap_element *b_elt = b->first;
1634   bitmap_element *dst_prev = NULL;
1635
1636   gcc_assert (dst != a && dst != b);
1637   if (a == b)
1638     {
1639       bitmap_clear (dst);
1640       return;
1641     }
1642
1643   while (a_elt || b_elt)
1644     {
1645       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1646         {
1647           /* Matching elts, generate A ^ B.  */
1648           unsigned ix;
1649           BITMAP_WORD ior = 0;
1650
1651           if (!dst_elt)
1652             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1653           else
1654             dst_elt->indx = a_elt->indx;
1655           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1656             {
1657               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1658
1659               ior |= r;
1660               dst_elt->bits[ix] = r;
1661             }
1662           a_elt = a_elt->next;
1663           b_elt = b_elt->next;
1664           if (ior)
1665             {
1666               dst_prev = dst_elt;
1667               dst_elt = dst_elt->next;
1668             }
1669         }
1670       else
1671         {
1672           /* Copy a single element.  */
1673           const bitmap_element *src;
1674
1675           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1676             {
1677               src = a_elt;
1678               a_elt = a_elt->next;
1679             }
1680           else
1681             {
1682               src = b_elt;
1683               b_elt = b_elt->next;
1684             }
1685
1686           if (!dst_elt)
1687             dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1688           else
1689             dst_elt->indx = src->indx;
1690           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1691           dst_prev = dst_elt;
1692           dst_elt = dst_elt->next;
1693         }
1694     }
1695   /* Ensure that dst->current is valid.  */
1696   dst->current = dst->first;
1697   bitmap_elt_clear_from (dst, dst_elt);
1698   gcc_checking_assert (!dst->current == !dst->first);
1699   if (dst->current)
1700     dst->indx = dst->current->indx;
1701 }
1702
1703 /* A ^= B */
1704
1705 void
1706 bitmap_xor_into (bitmap a, const_bitmap b)
1707 {
1708   bitmap_element *a_elt = a->first;
1709   const bitmap_element *b_elt = b->first;
1710   bitmap_element *a_prev = NULL;
1711
1712   if (a == b)
1713     {
1714       bitmap_clear (a);
1715       return;
1716     }
1717
1718   while (b_elt)
1719     {
1720       if (!a_elt || b_elt->indx < a_elt->indx)
1721         {
1722           /* Copy b_elt.  */
1723           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1724           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1725           a_prev = dst;
1726           b_elt = b_elt->next;
1727         }
1728       else if (a_elt->indx < b_elt->indx)
1729         {
1730           a_prev = a_elt;
1731           a_elt = a_elt->next;
1732         }
1733       else
1734         {
1735           /* Matching elts, generate A ^= B.  */
1736           unsigned ix;
1737           BITMAP_WORD ior = 0;
1738           bitmap_element *next = a_elt->next;
1739
1740           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1741             {
1742               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1743
1744               ior |= r;
1745               a_elt->bits[ix] = r;
1746             }
1747           b_elt = b_elt->next;
1748           if (ior)
1749             a_prev = a_elt;
1750           else
1751             bitmap_element_free (a, a_elt);
1752           a_elt = next;
1753         }
1754     }
1755   gcc_checking_assert (!a->current == !a->first);
1756   if (a->current)
1757     a->indx = a->current->indx;
1758 }
1759
1760 /* Return true if two bitmaps are identical.
1761    We do not bother with a check for pointer equality, as that never
1762    occurs in practice.  */
1763
1764 bool
1765 bitmap_equal_p (const_bitmap a, const_bitmap b)
1766 {
1767   const bitmap_element *a_elt;
1768   const bitmap_element *b_elt;
1769   unsigned ix;
1770
1771   for (a_elt = a->first, b_elt = b->first;
1772        a_elt && b_elt;
1773        a_elt = a_elt->next, b_elt = b_elt->next)
1774     {
1775       if (a_elt->indx != b_elt->indx)
1776         return false;
1777       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1778         if (a_elt->bits[ix] != b_elt->bits[ix])
1779           return false;
1780     }
1781   return !a_elt && !b_elt;
1782 }
1783
1784 /* Return true if A AND B is not empty.  */
1785
1786 bool
1787 bitmap_intersect_p (const_bitmap a, const_bitmap b)
1788 {
1789   const bitmap_element *a_elt;
1790   const bitmap_element *b_elt;
1791   unsigned ix;
1792
1793   for (a_elt = a->first, b_elt = b->first;
1794        a_elt && b_elt;)
1795     {
1796       if (a_elt->indx < b_elt->indx)
1797         a_elt = a_elt->next;
1798       else if (b_elt->indx < a_elt->indx)
1799         b_elt = b_elt->next;
1800       else
1801         {
1802           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1803             if (a_elt->bits[ix] & b_elt->bits[ix])
1804               return true;
1805           a_elt = a_elt->next;
1806           b_elt = b_elt->next;
1807         }
1808     }
1809   return false;
1810 }
1811
1812 /* Return true if A AND NOT B is not empty.  */
1813
1814 bool
1815 bitmap_intersect_compl_p (const_bitmap a, const_bitmap b)
1816 {
1817   const bitmap_element *a_elt;
1818   const bitmap_element *b_elt;
1819   unsigned ix;
1820   for (a_elt = a->first, b_elt = b->first;
1821        a_elt && b_elt;)
1822     {
1823       if (a_elt->indx < b_elt->indx)
1824         return true;
1825       else if (b_elt->indx < a_elt->indx)
1826         b_elt = b_elt->next;
1827       else
1828         {
1829           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1830             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1831               return true;
1832           a_elt = a_elt->next;
1833           b_elt = b_elt->next;
1834         }
1835     }
1836   return a_elt != NULL;
1837 }
1838
1839 \f
1840 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1841
1842 bool
1843 bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill)
1844 {
1845   bool changed = false;
1846
1847   bitmap_element *dst_elt = dst->first;
1848   const bitmap_element *a_elt = a->first;
1849   const bitmap_element *b_elt = b->first;
1850   const bitmap_element *kill_elt = kill->first;
1851   bitmap_element *dst_prev = NULL;
1852   bitmap_element **dst_prev_pnext = &dst->first;
1853
1854   gcc_assert (dst != a && dst != b && dst != kill);
1855
1856   /* Special cases.  We don't bother checking for bitmap_equal_p (b, kill).  */
1857   if (b == kill || bitmap_empty_p (b))
1858     {
1859       changed = !bitmap_equal_p (dst, a);
1860       if (changed)
1861         bitmap_copy (dst, a);
1862       return changed;
1863     }
1864   if (bitmap_empty_p (kill))
1865     return bitmap_ior (dst, a, b);
1866   if (bitmap_empty_p (a))
1867     return bitmap_and_compl (dst, b, kill);
1868
1869   while (a_elt || b_elt)
1870     {
1871       bool new_element = false;
1872
1873       if (b_elt)
1874         while (kill_elt && kill_elt->indx < b_elt->indx)
1875           kill_elt = kill_elt->next;
1876
1877       if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
1878           && (!a_elt || a_elt->indx >= b_elt->indx))
1879         {
1880           bitmap_element tmp_elt;
1881           unsigned ix;
1882
1883           BITMAP_WORD ior = 0;
1884           tmp_elt.indx = b_elt->indx;
1885           for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
1886             {
1887               BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
1888               ior |= r;
1889               tmp_elt.bits[ix] = r;
1890             }
1891
1892           if (ior)
1893             {
1894               changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1895                                         a_elt, &tmp_elt, changed);
1896               new_element = true;
1897               if (a_elt && a_elt->indx == b_elt->indx)
1898                 a_elt = a_elt->next;
1899             }
1900
1901           b_elt = b_elt->next;
1902           kill_elt = kill_elt->next;
1903         }
1904       else
1905         {
1906           changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
1907                                     a_elt, b_elt, changed);
1908           new_element = true;
1909
1910           if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1911             {
1912               a_elt = a_elt->next;
1913               b_elt = b_elt->next;
1914             }
1915           else
1916             {
1917               if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
1918                 a_elt = a_elt->next;
1919               else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
1920                 b_elt = b_elt->next;
1921             }
1922         }
1923
1924       if (new_element)
1925         {
1926           dst_prev = *dst_prev_pnext;
1927           dst_prev_pnext = &dst_prev->next;
1928           dst_elt = *dst_prev_pnext;
1929         }
1930     }
1931
1932   if (dst_elt)
1933     {
1934       changed = true;
1935       bitmap_elt_clear_from (dst, dst_elt);
1936     }
1937   gcc_checking_assert (!dst->current == !dst->first);
1938   if (dst->current)
1939     dst->indx = dst->current->indx;
1940
1941   return changed;
1942 }
1943
1944 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1945
1946 bool
1947 bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2)
1948 {
1949   bitmap_head tmp;
1950   bool changed;
1951
1952   bitmap_initialize (&tmp, &bitmap_default_obstack);
1953   bitmap_and_compl (&tmp, from1, from2);
1954   changed = bitmap_ior_into (a, &tmp);
1955   bitmap_clear (&tmp);
1956
1957   return changed;
1958 }
1959
1960 /* A |= (B & C).  Return true if A changes.  */
1961
1962 bool
1963 bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c)
1964 {
1965   bitmap_element *a_elt = a->first;
1966   const bitmap_element *b_elt = b->first;
1967   const bitmap_element *c_elt = c->first;
1968   bitmap_element and_elt;
1969   bitmap_element *a_prev = NULL;
1970   bitmap_element **a_prev_pnext = &a->first;
1971   bool changed = false;
1972   unsigned ix;
1973
1974   if (b == c)
1975     return bitmap_ior_into (a, b);
1976   if (bitmap_empty_p (b) || bitmap_empty_p (c))
1977     return false;
1978
1979   and_elt.indx = -1;
1980   while (b_elt && c_elt)
1981     {
1982       BITMAP_WORD overall;
1983
1984       /* Find a common item of B and C.  */
1985       while (b_elt->indx != c_elt->indx)
1986         {
1987           if (b_elt->indx < c_elt->indx)
1988             {
1989               b_elt = b_elt->next;
1990               if (!b_elt)
1991                 goto done;
1992             }
1993           else
1994             {
1995               c_elt = c_elt->next;
1996               if (!c_elt)
1997                 goto done;
1998             }
1999         }
2000
2001       overall = 0;
2002       and_elt.indx = b_elt->indx;
2003       for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++)
2004         {
2005           and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix];
2006           overall |= and_elt.bits[ix];
2007         }
2008
2009       b_elt = b_elt->next;
2010       c_elt = c_elt->next;
2011       if (!overall)
2012         continue;
2013
2014       /* Now find a place to insert AND_ELT.  */
2015       do
2016         {
2017           ix = a_elt ? a_elt->indx : and_elt.indx;
2018           if (ix == and_elt.indx)
2019             changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed);
2020           else if (ix > and_elt.indx)
2021             changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed);
2022
2023           a_prev = *a_prev_pnext;
2024           a_prev_pnext = &a_prev->next;
2025           a_elt = *a_prev_pnext;
2026
2027           /* If A lagged behind B/C, we advanced it so loop once more.  */
2028         }
2029       while (ix < and_elt.indx);
2030     }
2031
2032  done:
2033   gcc_checking_assert (!a->current == !a->first);
2034   if (a->current)
2035     a->indx = a->current->indx;
2036   return changed;
2037 }
2038 \f
2039 /* Debugging function to print out the contents of a bitmap.  */
2040
2041 DEBUG_FUNCTION void
2042 debug_bitmap_file (FILE *file, const_bitmap head)
2043 {
2044   const bitmap_element *ptr;
2045
2046   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
2047            " current = " HOST_PTR_PRINTF " indx = %u\n",
2048            (void *) head->first, (void *) head->current, head->indx);
2049
2050   for (ptr = head->first; ptr; ptr = ptr->next)
2051     {
2052       unsigned int i, j, col = 26;
2053
2054       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
2055                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
2056                (const void*) ptr, (const void*) ptr->next,
2057                (const void*) ptr->prev, ptr->indx);
2058
2059       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
2060         for (j = 0; j < BITMAP_WORD_BITS; j++)
2061           if ((ptr->bits[i] >> j) & 1)
2062             {
2063               if (col > 70)
2064                 {
2065                   fprintf (file, "\n\t\t\t");
2066                   col = 24;
2067                 }
2068
2069               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
2070                                      + i * BITMAP_WORD_BITS + j));
2071               col += 4;
2072             }
2073
2074       fprintf (file, " }\n");
2075     }
2076 }
2077
2078 /* Function to be called from the debugger to print the contents
2079    of a bitmap.  */
2080
2081 DEBUG_FUNCTION void
2082 debug_bitmap (const_bitmap head)
2083 {
2084   debug_bitmap_file (stdout, head);
2085 }
2086
2087 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
2088    it does not print anything but the bits.  */
2089
2090 DEBUG_FUNCTION void
2091 bitmap_print (FILE *file, const_bitmap head, const char *prefix, const char *suffix)
2092 {
2093   const char *comma = "";
2094   unsigned i;
2095   bitmap_iterator bi;
2096
2097   fputs (prefix, file);
2098   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
2099     {
2100       fprintf (file, "%s%d", comma, i);
2101       comma = ", ";
2102     }
2103   fputs (suffix, file);
2104 }
2105 #ifdef GATHER_STATISTICS
2106
2107
2108 /* Used to accumulate statistics about bitmap sizes.  */
2109 struct output_info
2110 {
2111   HOST_WIDEST_INT size;
2112   int count;
2113 };
2114
2115 /* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
2116    and update statistics.  */
2117 static int
2118 print_statistics (void **slot, void *b)
2119 {
2120   struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
2121   struct output_info *i = (struct output_info *) b;
2122   char s[4096];
2123
2124   if (d->allocated)
2125     {
2126       const char *s1 = d->file;
2127       const char *s2;
2128       while ((s2 = strstr (s1, "gcc/")))
2129         s1 = s2 + 4;
2130       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
2131       s[41] = 0;
2132       fprintf (stderr, "%-41s %8d %15"HOST_WIDEST_INT_PRINT"d %15"
2133                HOST_WIDEST_INT_PRINT"d %15"HOST_WIDEST_INT_PRINT"d %10d %10d\n",
2134                s, d->created, d->allocated, d->peak, d->current, d->nsearches,
2135                d->search_iter);
2136       i->size += d->allocated;
2137       i->count += d->created;
2138     }
2139   return 1;
2140 }
2141 #endif
2142 /* Output per-bitmap memory usage statistics.  */
2143 void
2144 dump_bitmap_statistics (void)
2145 {
2146 #ifdef GATHER_STATISTICS
2147   struct output_info info;
2148
2149   if (!bitmap_desc_hash)
2150     return;
2151
2152   fprintf (stderr, "\nBitmap                                     Overall "
2153                    "      Allocated            Peak            Leak   searched "
2154                    "  search itr\n");
2155   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2156   info.count = 0;
2157   info.size = 0;
2158   htab_traverse (bitmap_desc_hash, print_statistics, &info);
2159   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2160   fprintf (stderr, "%-40s %9d %15"HOST_WIDEST_INT_PRINT"d\n",
2161            "Total", info.count, info.size);
2162   fprintf (stderr, "---------------------------------------------------------------------------------\n");
2163 #endif
2164 }
2165
2166 /* Compute hash of bitmap (for purposes of hashing).  */
2167 hashval_t
2168 bitmap_hash (const_bitmap head)
2169 {
2170   const bitmap_element *ptr;
2171   BITMAP_WORD hash = 0;
2172   int ix;
2173
2174   for (ptr = head->first; ptr; ptr = ptr->next)
2175     {
2176       hash ^= ptr->indx;
2177       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
2178         hash ^= ptr->bits[ix];
2179     }
2180   return (hashval_t)hash;
2181 }
2182
2183 #include "gt-bitmap.h"