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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "obstack.h"
  29 #include "ggc.h"
  30 #include "bitmap.h"
  31 #include "hashtab.h"
  32
  33 #ifdef GATHER_STATISTICS
  34
  35 /* Store information about each particular bitmap.  */
  36 struct bitmap_descriptor
  37 {
  38   const char *function;
  39   const char *file;
  40   int line;
  41   int allocated;
  42   int created;
  43   int peak;
  44   int current;
  45   int nsearches;
  46 };
  47
  48 /* Hashtable mapping bitmap names to descriptors.  */
  49 static htab_t bitmap_desc_hash;
  50
  51 /* Hashtable helpers.  */
  52 static hashval_t
  53 hash_descriptor (const void *p)
  54 {
  55   const struct bitmap_descriptor *d = p;
  56   return htab_hash_pointer (d->file) + d->line;
  57 }
  58 struct loc
  59 {
  60   const char *file;
  61   const char *function;
  62   int line;
  63 };
  64 static int
  65 eq_descriptor (const void *p1, const void *p2)
  66 {
  67   const struct bitmap_descriptor *d = p1;
  68   const struct loc *l = p2;
  69   return d->file == l->file && d->function == l->function && d->line == l->line;
  70 }
  71
  72 /* For given file and line, return descriptor, create new if needed.  */
  73 static struct bitmap_descriptor *
  74 bitmap_descriptor (const char *file, const char *function, int line)
  75 {
  76   struct bitmap_descriptor **slot;
  77   struct loc loc;
  78
  79   loc.file = file;
  80   loc.function = function;
  81   loc.line = line;
  82
  83   if (!bitmap_desc_hash)
  84     bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
  85
  86   slot = (struct bitmap_descriptor **)
  87     htab_find_slot_with_hash (bitmap_desc_hash, &loc,
  88                               htab_hash_pointer (file) + line,
  89                               1);
  90   if (*slot)
  91     return *slot;
  92   *slot = xcalloc (sizeof (**slot), 1);
  93   (*slot)->file = file;
  94   (*slot)->function = function;
  95   (*slot)->line = line;
  96   return *slot;
  97 }
  98
  99 /* Register new bitmap.  */
 100 void
 101 bitmap_register (bitmap b MEM_STAT_DECL)
 102 {
 103   b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line);
 104   b->desc->created++;
 105 }
 106
 107 /* Account the overhead.  */
 108 static void
 109 register_overhead (bitmap b, int amount)
 110 {
 111   b->desc->current += amount;
 112   if (amount > 0)
 113     b->desc->allocated += amount;
 114   gcc_assert (b->desc->current >= 0);
 115   if (b->desc->peak < b->desc->current)
 116     b->desc->peak = b->desc->current;
 117 }
 118 #endif
 119
 120 /* Global data */
 121 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
 122 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
 123 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
 124                                                             GC'd elements.  */
 125
 126 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
 127 static void bitmap_element_free (bitmap, bitmap_element *);
 128 static bitmap_element *bitmap_element_allocate (bitmap);
 129 static int bitmap_element_zerop (bitmap_element *);
 130 static void bitmap_element_link (bitmap, bitmap_element *);
 131 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int);
 132 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
 133 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
 134 \f
 135
 136 /* Add ELEM to the appropriate freelist.  */
 137 static inline void
 138 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
 139 {
 140   bitmap_obstack *bit_obstack = head->obstack;
 141
 142   elt->next = NULL;
 143   if (bit_obstack)
 144     {
 145       elt->prev = bit_obstack->elements;
 146       bit_obstack->elements = elt;
 147     }
 148   else
 149     {
 150       elt->prev = bitmap_ggc_free;
 151       bitmap_ggc_free = elt;
 152     }
 153 }
 154
 155 /* Free a bitmap element.  Since these are allocated off the
 156    bitmap_obstack, "free" actually means "put onto the freelist".  */
 157
 158 static inline void
 159 bitmap_element_free (bitmap head, bitmap_element *elt)
 160 {
 161   bitmap_element *next = elt->next;
 162   bitmap_element *prev = elt->prev;
 163
 164   if (prev)
 165     prev->next = next;
 166
 167   if (next)
 168     next->prev = prev;
 169
 170   if (head->first == elt)
 171     head->first = next;
 172
 173   /* Since the first thing we try is to insert before current,
 174      make current the next entry in preference to the previous.  */
 175   if (head->current == elt)
 176     {
 177       head->current = next != 0 ? next : prev;
 178       if (head->current)
 179         head->indx = head->current->indx;
 180       else
 181         head->indx = 0;
 182     }
 183 #ifdef GATHER_STATISTICS
 184   register_overhead (head, -((int)sizeof (bitmap_element)));
 185 #endif
 186   bitmap_elem_to_freelist (head, elt);
 187 }
 188 \f
 189 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 190
 191 static inline bitmap_element *
 192 bitmap_element_allocate (bitmap head)
 193 {
 194   bitmap_element *element;
 195   bitmap_obstack *bit_obstack = head->obstack;
 196
 197   if (bit_obstack)
 198     {
 199       element = bit_obstack->elements;
 200
 201       if (element)
 202         /* Use up the inner list first before looking at the next
 203            element of the outer list.  */
 204         if (element->next)
 205           {
 206             bit_obstack->elements = element->next;
 207             bit_obstack->elements->prev = element->prev;
 208           }
 209         else
 210           /*  Inner list was just a singleton.  */
 211           bit_obstack->elements = element->prev;
 212       else
 213         element = XOBNEW (&bit_obstack->obstack, bitmap_element);
 214     }
 215   else
 216     {
 217       element = bitmap_ggc_free;
 218       if (element)
 219         /* Use up the inner list first before looking at the next
 220            element of the outer list.  */
 221         if (element->next)
 222           {
 223             bitmap_ggc_free = element->next;
 224             bitmap_ggc_free->prev = element->prev;
 225           }
 226         else
 227           /*  Inner list was just a singleton.  */
 228           bitmap_ggc_free = element->prev;
 229       else
 230         element = GGC_NEW (bitmap_element);
 231     }
 232
 233 #ifdef GATHER_STATISTICS
 234   register_overhead (head, sizeof (bitmap_element));
 235 #endif
 236   memset (element->bits, 0, sizeof (element->bits));
 237
 238   return element;
 239 }
 240
 241 /* Remove ELT and all following elements from bitmap HEAD.  */
 242
 243 void
 244 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 245 {
 246   bitmap_element *prev;
 247   bitmap_obstack *bit_obstack = head->obstack;
 248 #ifdef GATHER_STATISTICS
 249   int n;
 250 #endif
 251
 252   if (!elt) return;
 253 #ifdef GATHER_STATISTICS
 254   n = 0;
 255   for (prev = elt; prev; prev = prev->next)
 256     n++;
 257   register_overhead (head, -sizeof (bitmap_element) * n);
 258 #endif
 259
 260   prev = elt->prev;
 261   if (prev)
 262     {
 263       prev->next = NULL;
 264       if (head->current->indx > prev->indx)
 265         {
 266           head->current = prev;
 267           head->indx = prev->indx;
 268         }
 269     }
 270   else
 271     {
 272       head->first = NULL;
 273       head->current = NULL;
 274       head->indx = 0;
 275     }
 276
 277   /* Put the entire list onto the free list in one operation. */
 278   if (bit_obstack)
 279     {
 280       elt->prev = bit_obstack->elements;
 281       bit_obstack->elements = elt;
 282     }
 283   else
 284     {
 285       elt->prev = bitmap_ggc_free;
 286       bitmap_ggc_free = elt;
 287     }
 288 }
 289
 290 /* Clear a bitmap by freeing the linked list.  */
 291
 292 inline void
 293 bitmap_clear (bitmap head)
 294 {
 295   if (head->first)
 296     bitmap_elt_clear_from (head, head->first);
 297 }
 298 \f
 299 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
 300    the default bitmap obstack.  */
 301
 302 void
 303 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
 304 {
 305   if (!bit_obstack)
 306     bit_obstack = &bitmap_default_obstack;
 307
 308 #if !defined(__GNUC__) || (__GNUC__ < 2)
 309 #define __alignof__(type) 0
 310 #endif
 311
 312   bit_obstack->elements = NULL;
 313   bit_obstack->heads = NULL;
 314   obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
 315                               __alignof__ (bitmap_element),
 316                               obstack_chunk_alloc,
 317                               obstack_chunk_free);
 318 }
 319
 320 /* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
 321    release the default bitmap obstack.  */
 322
 323 void
 324 bitmap_obstack_release (bitmap_obstack *bit_obstack)
 325 {
 326   if (!bit_obstack)
 327     bit_obstack = &bitmap_default_obstack;
 328
 329   bit_obstack->elements = NULL;
 330   bit_obstack->heads = NULL;
 331   obstack_free (&bit_obstack->obstack, NULL);
 332 }
 333
 334 /* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
 335    it on the default bitmap obstack.  */
 336
 337 bitmap
 338 bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
 339 {
 340   bitmap map;
 341
 342   if (!bit_obstack)
 343     bit_obstack = &bitmap_default_obstack;
 344   map = bit_obstack->heads;
 345   if (map)
 346     bit_obstack->heads = (void *)map->first;
 347   else
 348     map = XOBNEW (&bit_obstack->obstack, bitmap_head);
 349   bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
 350 #ifdef GATHER_STATISTICS
 351   register_overhead (map, sizeof (bitmap_head));
 352 #endif
 353
 354   return map;
 355 }
 356
 357 /* Create a new GCd bitmap.  */
 358
 359 bitmap
 360 bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
 361 {
 362   bitmap map;
 363
 364   map = GGC_NEW (struct bitmap_head_def);
 365   bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
 366 #ifdef GATHER_STATISTICS
 367   register_overhead (map, sizeof (bitmap_head));
 368 #endif
 369
 370   return map;
 371 }
 372
 373 /* Release an obstack allocated bitmap.  */
 374
 375 void
 376 bitmap_obstack_free (bitmap map)
 377 {
 378   if (map)
 379     {
 380       bitmap_clear (map);
 381       map->first = (void *)map->obstack->heads;
 382 #ifdef GATHER_STATISTICS
 383       register_overhead (map, -((int)sizeof (bitmap_head)));
 384 #endif
 385       map->obstack->heads = map;
 386     }
 387 }
 388
 389 \f
 390 /* Return nonzero if all bits in an element are zero.  */
 391
 392 static inline int
 393 bitmap_element_zerop (bitmap_element *element)
 394 {
 395 #if BITMAP_ELEMENT_WORDS == 2
 396   return (element->bits[0] | element->bits[1]) == 0;
 397 #else
 398   unsigned i;
 399
 400   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 401     if (element->bits[i] != 0)
 402       return 0;
 403
 404   return 1;
 405 #endif
 406 }
 407 \f
 408 /* Link the bitmap element into the current bitmap linked list.  */
 409
 410 static inline void
 411 bitmap_element_link (bitmap head, bitmap_element *element)
 412 {
 413   unsigned int indx = element->indx;
 414   bitmap_element *ptr;
 415
 416   /* If this is the first and only element, set it in.  */
 417   if (head->first == 0)
 418     {
 419       element->next = element->prev = 0;
 420       head->first = element;
 421     }
 422
 423   /* If this index is less than that of the current element, it goes someplace
 424      before the current element.  */
 425   else if (indx < head->indx)
 426     {
 427       for (ptr = head->current;
 428            ptr->prev != 0 && ptr->prev->indx > indx;
 429            ptr = ptr->prev)
 430         ;
 431
 432       if (ptr->prev)
 433         ptr->prev->next = element;
 434       else
 435         head->first = element;
 436
 437       element->prev = ptr->prev;
 438       element->next = ptr;
 439       ptr->prev = element;
 440     }
 441
 442   /* Otherwise, it must go someplace after the current element.  */
 443   else
 444     {
 445       for (ptr = head->current;
 446            ptr->next != 0 && ptr->next->indx < indx;
 447            ptr = ptr->next)
 448         ;
 449
 450       if (ptr->next)
 451         ptr->next->prev = element;
 452
 453       element->next = ptr->next;
 454       element->prev = ptr;
 455       ptr->next = element;
 456     }
 457
 458   /* Set up so this is the first element searched.  */
 459   head->current = element;
 460   head->indx = indx;
 461 }
 462
 463 /* Insert a new uninitialized element into bitmap HEAD after element
 464    ELT.  If ELT is NULL, insert the element at the start.  Return the
 465    new element.  */
 466
 467 static bitmap_element *
 468 bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx)
 469 {
 470   bitmap_element *node = bitmap_element_allocate (head);
 471   node->indx = indx;
 472
 473   if (!elt)
 474     {
 475       if (!head->current)
 476         {
 477           head->current = node;
 478           head->indx = indx;
 479         }
 480       node->next = head->first;
 481       if (node->next)
 482         node->next->prev = node;
 483       head->first = node;
 484       node->prev = NULL;
 485     }
 486   else
 487     {
 488       gcc_assert (head->current);
 489       node->next = elt->next;
 490       if (node->next)
 491         node->next->prev = node;
 492       elt->next = node;
 493       node->prev = elt;
 494     }
 495   return node;
 496 }
 497 \f
 498 /* Copy a bitmap to another bitmap.  */
 499
 500 void
 501 bitmap_copy (bitmap to, bitmap from)
 502 {
 503   bitmap_element *from_ptr, *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 *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 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 (bitmap a)
 675 {
 676   unsigned long count = 0;
 677   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 (bitmap a)
 703 {
 704   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, bitmap a, bitmap b)
 754 {
 755   bitmap_element *dst_elt = dst->first;
 756   bitmap_element *a_elt = a->first;
 757   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, bitmap b)
 812 {
 813   bitmap_element *a_elt = a->first;
 814   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                  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, bitmap a, bitmap b)
 893 {
 894   bitmap_element *dst_elt = dst->first;
 895   bitmap_element *a_elt = a->first;
 896   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, bitmap b)
1006 {
1007   bitmap_element *a_elt = a->first;
1008   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, bitmap b)
1286 {
1287   bitmap_element *a_elt = a->first;
1288   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                 bitmap_element *a_elt, 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       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, bitmap a, bitmap b)
1415 {
1416   bitmap_element *dst_elt = dst->first;
1417   bitmap_element *a_elt = a->first;
1418   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, bitmap b)
1462 {
1463   bitmap_element *a_elt = a->first;
1464   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, bitmap a, bitmap b)
1501 {
1502   bitmap_element *dst_elt = dst->first;
1503   bitmap_element *a_elt = a->first;
1504   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           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, bitmap b)
1578 {
1579   bitmap_element *a_elt = a->first;
1580   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 (bitmap a, bitmap b)
1637 {
1638   bitmap_element *a_elt;
1639   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 (bitmap a, bitmap b)
1659 {
1660   bitmap_element *a_elt;
1661   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 (bitmap a, bitmap b)
1687 {
1688   bitmap_element *a_elt;
1689   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, bitmap a, bitmap b, bitmap kill)
1715 {
1716   bool changed = false;
1717
1718   bitmap_element *dst_elt = dst->first;
1719   bitmap_element *a_elt = a->first;
1720   bitmap_element *b_elt = b->first;
1721   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, bitmap from1, 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, bitmap head)
1836 {
1837   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                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1848
1849       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1850         for (j = 0; j < BITMAP_WORD_BITS; j++)
1851           if ((ptr->bits[i] >> j) & 1)
1852             {
1853               if (col > 70)
1854                 {
1855                   fprintf (file, "\n\t\t\t");
1856                   col = 24;
1857                 }
1858
1859               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1860                                      + i * BITMAP_WORD_BITS + j));
1861               col += 4;
1862             }
1863
1864       fprintf (file, " }\n");
1865     }
1866 }
1867
1868 /* Function to be called from the debugger to print the contents
1869    of a bitmap.  */
1870
1871 void
1872 debug_bitmap (bitmap head)
1873 {
1874   debug_bitmap_file (stdout, head);
1875 }
1876
1877 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1878    it does not print anything but the bits.  */
1879
1880 void
1881 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1882 {
1883   const char *comma = "";
1884   unsigned i;
1885   bitmap_iterator bi;
1886
1887   fputs (prefix, file);
1888   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1889     {
1890       fprintf (file, "%s%d", comma, i);
1891       comma = ", ";
1892     }
1893   fputs (suffix, file);
1894 }
1895 #ifdef GATHER_STATISTICS
1896
1897
1898 /* Used to accumulate statistics about bitmap sizes.  */
1899 struct output_info
1900 {
1901   int count;
1902   int size;
1903 };
1904
1905 /* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
1906    and update statistics.  */
1907 static int
1908 print_statistics (void **slot, void *b)
1909 {
1910   struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
1911   struct output_info *i = (struct output_info *) b;
1912   char s[4096];
1913
1914   if (d->allocated)
1915     {
1916       const char *s1 = d->file;
1917       const char *s2;
1918       while ((s2 = strstr (s1, "gcc/")))
1919         s1 = s2 + 4;
1920       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
1921       s[41] = 0;
1922       fprintf (stderr, "%-41s %6d %10d %10d %10d %10d\n", s,
1923                d->created, d->allocated, d->peak, d->current, d->nsearches);
1924       i->size += d->allocated;
1925       i->count += d->created;
1926     }
1927   return 1;
1928 }
1929 #endif
1930 /* Output per-bitmap memory usage statistics.  */
1931 void
1932 dump_bitmap_statistics (void)
1933 {
1934 #ifdef GATHER_STATISTICS
1935   struct output_info info;
1936
1937   if (!bitmap_desc_hash)
1938     return;
1939
1940   fprintf (stderr, "\nBitmap                                     Overall "
1941                    "Allocated     Peak        Leak   searched "
1942                    "  per search\n");
1943   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1944   info.count = 0;
1945   info.size = 0;
1946   htab_traverse (bitmap_desc_hash, print_statistics, &info);
1947   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1948   fprintf (stderr, "%-40s %7d %10d\n",
1949            "Total", info.count, info.size);
1950   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1951 #endif
1952 }
1953
1954 /* Compute hash of bitmap (for purposes of hashing).  */
1955 hashval_t
1956 bitmap_hash (bitmap head)
1957 {
1958   bitmap_element *ptr;
1959   BITMAP_WORD hash = 0;
1960   int ix;
1961
1962   for (ptr = head->first; ptr; ptr = ptr->next)
1963     {
1964       hash ^= ptr->indx;
1965       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1966         hash ^= ptr->bits[ix];
1967     }
1968   return (hashval_t)hash;
1969 }
1970
1971 #include "gt-bitmap.h"