gcc/bitmap.c

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