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