gcc/bitmap.c

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