gcc/bitmap.c

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