gcc/bitmap.c

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