gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
   3    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 /* DST = A & ~B  */
 856
 857 void
 858 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 859 {
 860   bitmap_element *dst_elt = dst->first;
 861   bitmap_element *a_elt = a->first;
 862   bitmap_element *b_elt = b->first;
 863   bitmap_element *dst_prev = NULL;
 864
 865   gcc_assert (dst != a && dst != b);
 866
 867   if (a == b)
 868     {
 869       bitmap_clear (dst);
 870       return;
 871     }
 872
 873   while (a_elt)
 874     {
 875       if (!b_elt || a_elt->indx < b_elt->indx)
 876         {
 877           /* Copy a_elt.  */
 878           if (!dst_elt)
 879             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 880           else
 881             dst_elt->indx = a_elt->indx;
 882           memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 883           dst_prev = dst_elt;
 884           dst_elt = dst_elt->next;
 885           a_elt = a_elt->next;
 886         }
 887       else if (b_elt->indx < a_elt->indx)
 888         b_elt = b_elt->next;
 889       else
 890         {
 891           /* Matching elts, generate A & ~B.  */
 892           unsigned ix;
 893           BITMAP_WORD ior = 0;
 894
 895           if (!dst_elt)
 896             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
 897           else
 898             dst_elt->indx = a_elt->indx;
 899           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 900             {
 901               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 902
 903               dst_elt->bits[ix] = r;
 904               ior |= r;
 905             }
 906           if (ior)
 907             {
 908               dst_prev = dst_elt;
 909               dst_elt = dst_elt->next;
 910             }
 911           a_elt = a_elt->next;
 912           b_elt = b_elt->next;
 913         }
 914     }
 915   /* Ensure that dst->current is valid.  */
 916   dst->current = dst->first;
 917   bitmap_elt_clear_from (dst, dst_elt);
 918   gcc_assert (!dst->current == !dst->first);
 919   if (dst->current)
 920     dst->indx = dst->current->indx;
 921 }
 922
 923 /* A &= ~B. Returns true if A changes */
 924
 925 bool
 926 bitmap_and_compl_into (bitmap a, bitmap b)
 927 {
 928   bitmap_element *a_elt = a->first;
 929   bitmap_element *b_elt = b->first;
 930   bitmap_element *next;
 931   BITMAP_WORD changed = 0;
 932
 933   if (a == b)
 934     {
 935       if (bitmap_empty_p (a))
 936         return false;
 937       else
 938         {
 939           bitmap_clear (a);
 940           return true;
 941         }
 942     }
 943
 944   while (a_elt && b_elt)
 945     {
 946       if (a_elt->indx < b_elt->indx)
 947         a_elt = a_elt->next;
 948       else if (b_elt->indx < a_elt->indx)
 949         b_elt = b_elt->next;
 950       else
 951         {
 952           /* Matching elts, generate A &= ~B.  */
 953           unsigned ix;
 954           BITMAP_WORD ior = 0;
 955
 956           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 957             {
 958               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
 959               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
 960
 961               a_elt->bits[ix] = r;
 962               changed |= cleared;
 963               ior |= r;
 964             }
 965           next = a_elt->next;
 966           if (!ior)
 967             bitmap_element_free (a, a_elt);
 968           a_elt = next;
 969           b_elt = b_elt->next;
 970         }
 971     }
 972   gcc_assert (!a->current == !a->first);
 973   gcc_assert (!a->current || a->indx == a->current->indx);
 974   return changed != 0;
 975 }
 976
 977 /* Clear COUNT bits from START in HEAD.  */
 978 void
 979 bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
 980 {
 981   unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
 982   unsigned int end_bit_plus1 = start + count;
 983   unsigned int end_bit = end_bit_plus1 - 1;
 984   unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
 985   bitmap_element *elt = bitmap_find_bit (head, start);
 986
 987   /* If bitmap_find_bit returns zero, the current is the closest block
 988      to the result.  If the current is less than first index, find the
 989      next one.  Otherwise, just set elt to be current.  */
 990   if (!elt)
 991     {
 992       if (head->current)
 993         {
 994           if (head->indx < first_index)
 995             {
 996               elt = head->current->next;
 997               if (!elt)
 998                 return;
 999             }
1000           else
1001             elt = head->current;
1002         }
1003       else
1004         return;
1005     }
1006
1007   while (elt && (elt->indx <= last_index))
1008     {
1009       bitmap_element * next_elt = elt->next;
1010       unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS;
1011       unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
1012
1013
1014       if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
1015         /* Get rid of the entire elt and go to the next one.  */
1016         bitmap_element_free (head, elt);
1017       else
1018         {
1019           /* Going to have to knock out some bits in this elt.  */
1020           unsigned int first_word_to_mod;
1021           BITMAP_WORD first_mask;
1022           unsigned int last_word_to_mod;
1023           BITMAP_WORD last_mask;
1024           unsigned int i;
1025           bool clear = true;
1026
1027           if (elt_start_bit <= start)
1028             {
1029               /* The first bit to turn off is somewhere inside this
1030                  elt.  */
1031               first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
1032
1033               /* This mask should have 1s in all bits >= start position. */
1034               first_mask =
1035                 (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
1036               first_mask = ~first_mask;
1037             }
1038           else
1039             {
1040               /* The first bit to turn off is below this start of this elt.  */
1041               first_word_to_mod = 0;
1042               first_mask = 0;
1043               first_mask = ~first_mask;
1044             }
1045
1046           if (elt_end_bit_plus1 <= end_bit_plus1)
1047             {
1048               /* The last bit to turn off is beyond this elt.  */
1049               last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
1050               last_mask = 0;
1051               last_mask = ~last_mask;
1052             }
1053           else
1054             {
1055               /* The last bit to turn off is inside to this elt.  */
1056               last_word_to_mod =
1057                 (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
1058
1059               /* The last mask should have 1s below the end bit.  */
1060               last_mask =
1061                 (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
1062             }
1063
1064
1065           if (first_word_to_mod == last_word_to_mod)
1066             {
1067               BITMAP_WORD mask = first_mask & last_mask;
1068               elt->bits[first_word_to_mod] &= ~mask;
1069             }
1070           else
1071             {
1072               elt->bits[first_word_to_mod] &= ~first_mask;
1073               for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
1074                 elt->bits[i] = 0;
1075               elt->bits[last_word_to_mod] &= ~last_mask;
1076             }
1077           for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1078             if (elt->bits[i])
1079               {
1080                 clear = false;
1081                 break;
1082               }
1083           /* Check to see if there are any bits left.  */
1084           if (clear)
1085             bitmap_element_free (head, elt);
1086         }
1087       elt = next_elt;
1088     }
1089
1090   if (elt)
1091     {
1092       head->current = elt;
1093       head->indx = head->current->indx;
1094     }
1095 }
1096
1097 /* A = ~A & B. */
1098
1099 void
1100 bitmap_compl_and_into (bitmap a, bitmap b)
1101 {
1102   bitmap_element *a_elt = a->first;
1103   bitmap_element *b_elt = b->first;
1104   bitmap_element *a_prev = NULL;
1105   bitmap_element *next;
1106
1107   gcc_assert (a != b);
1108
1109   if (bitmap_empty_p (a))
1110     {
1111       bitmap_copy (a, b);
1112       return;
1113     }
1114   if (bitmap_empty_p (b))
1115     {
1116       bitmap_clear (a);
1117       return;
1118     }
1119
1120   while (a_elt || b_elt)
1121     {
1122       if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1123         {
1124           /* A is before B.  Remove A */
1125           next = a_elt->next;
1126           a_prev = a_elt->prev;
1127           bitmap_element_free (a, a_elt);
1128           a_elt = next;
1129         }
1130       else if (!a_elt || b_elt->indx < a_elt->indx)
1131         {
1132           /* B is before A.  Copy B. */
1133           next = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1134           memcpy (next->bits, b_elt->bits, sizeof (next->bits));
1135           a_prev = next;
1136           b_elt = b_elt->next;
1137         }
1138       else
1139         {
1140           /* Matching elts, generate A = ~A & B.  */
1141           unsigned ix;
1142           BITMAP_WORD ior = 0;
1143
1144           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1145             {
1146               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
1147               BITMAP_WORD r = b_elt->bits[ix] ^ cleared;
1148
1149               a_elt->bits[ix] = r;
1150               ior |= r;
1151             }
1152           next = a_elt->next;
1153           if (!ior)
1154             bitmap_element_free (a, a_elt);
1155           else
1156             a_prev = a_elt;
1157           a_elt = next;
1158           b_elt = b_elt->next;
1159         }
1160     }
1161   gcc_assert (!a->current == !a->first);
1162   gcc_assert (!a->current || a->indx == a->current->indx);
1163   return;
1164 }
1165
1166 /* DST = A | B.  Return true if DST changes.  */
1167
1168 bool
1169 bitmap_ior (bitmap dst, bitmap a, bitmap b)
1170 {
1171   bitmap_element *dst_elt = dst->first;
1172   bitmap_element *a_elt = a->first;
1173   bitmap_element *b_elt = b->first;
1174   bitmap_element *dst_prev = NULL;
1175   bool changed = false;
1176
1177   gcc_assert (dst != a && dst != b);
1178
1179   while (a_elt || b_elt)
1180     {
1181       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1182         {
1183           /* Matching elts, generate A | B.  */
1184           unsigned ix;
1185
1186           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
1187             {
1188               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1189                 {
1190                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1191
1192                   if (r != dst_elt->bits[ix])
1193                     {
1194                       dst_elt->bits[ix] = r;
1195                       changed = true;
1196                     }
1197                 }
1198             }
1199           else
1200             {
1201               changed = true;
1202               if (!dst_elt)
1203                 dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1204               else
1205                 dst_elt->indx = a_elt->indx;
1206               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1207                 {
1208                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1209
1210                   dst_elt->bits[ix] = r;
1211                 }
1212             }
1213           a_elt = a_elt->next;
1214           b_elt = b_elt->next;
1215           dst_prev = dst_elt;
1216           dst_elt = dst_elt->next;
1217         }
1218       else
1219         {
1220           /* Copy a single element.  */
1221           bitmap_element *src;
1222
1223           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1224             {
1225               src = a_elt;
1226               a_elt = a_elt->next;
1227             }
1228           else
1229             {
1230               src = b_elt;
1231               b_elt = b_elt->next;
1232             }
1233
1234           if (!changed && dst_elt && dst_elt->indx == src->indx)
1235             {
1236               unsigned ix;
1237
1238               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1239                 if (src->bits[ix] != dst_elt->bits[ix])
1240                   {
1241                     dst_elt->bits[ix] = src->bits[ix];
1242                     changed = true;
1243                   }
1244             }
1245           else
1246             {
1247               changed = true;
1248               if (!dst_elt)
1249                 dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1250               else
1251                 dst_elt->indx = src->indx;
1252               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1253             }
1254
1255           dst_prev = dst_elt;
1256           dst_elt = dst_elt->next;
1257         }
1258     }
1259
1260   if (dst_elt)
1261     {
1262       changed = true;
1263       bitmap_elt_clear_from (dst, dst_elt);
1264     }
1265   gcc_assert (!dst->current == !dst->first);
1266   if (dst->current)
1267     dst->indx = dst->current->indx;
1268   return changed;
1269 }
1270
1271 /* A |= B.  Return true if A changes.  */
1272
1273 bool
1274 bitmap_ior_into (bitmap a, bitmap b)
1275 {
1276   bitmap_element *a_elt = a->first;
1277   bitmap_element *b_elt = b->first;
1278   bitmap_element *a_prev = NULL;
1279   bool changed = false;
1280
1281   if (a == b)
1282     return false;
1283
1284   while (b_elt)
1285     {
1286       if (!a_elt || b_elt->indx < a_elt->indx)
1287         {
1288           /* Copy b_elt.  */
1289           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1290           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1291           a_prev = dst;
1292           b_elt = b_elt->next;
1293           changed = true;
1294         }
1295       else if (a_elt->indx < b_elt->indx)
1296         {
1297           a_prev = a_elt;
1298           a_elt = a_elt->next;
1299         }
1300       else
1301         {
1302           /* Matching elts, generate A |= B.  */
1303           unsigned ix;
1304
1305           if (changed)
1306             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1307               {
1308                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1309
1310                 a_elt->bits[ix] = r;
1311               }
1312           else
1313             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1314               {
1315                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
1316
1317                 if (a_elt->bits[ix] != r)
1318                   {
1319                     changed = true;
1320                     a_elt->bits[ix] = r;
1321                   }
1322               }
1323           b_elt = b_elt->next;
1324           a_prev = a_elt;
1325           a_elt = a_elt->next;
1326         }
1327     }
1328   gcc_assert (!a->current == !a->first);
1329   if (a->current)
1330     a->indx = a->current->indx;
1331   return changed;
1332 }
1333
1334 /* DST = A ^ B  */
1335
1336 void
1337 bitmap_xor (bitmap dst, bitmap a, bitmap b)
1338 {
1339   bitmap_element *dst_elt = dst->first;
1340   bitmap_element *a_elt = a->first;
1341   bitmap_element *b_elt = b->first;
1342   bitmap_element *dst_prev = NULL;
1343
1344   gcc_assert (dst != a && dst != b);
1345   if (a == b)
1346     {
1347       bitmap_clear (dst);
1348       return;
1349     }
1350
1351   while (a_elt || b_elt)
1352     {
1353       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
1354         {
1355           /* Matching elts, generate A ^ B.  */
1356           unsigned ix;
1357           BITMAP_WORD ior = 0;
1358
1359           if (!dst_elt)
1360             dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
1361           else
1362             dst_elt->indx = a_elt->indx;
1363           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1364             {
1365               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1366
1367               ior |= r;
1368               dst_elt->bits[ix] = r;
1369             }
1370           a_elt = a_elt->next;
1371           b_elt = b_elt->next;
1372           if (ior)
1373             {
1374               dst_prev = dst_elt;
1375               dst_elt = dst_elt->next;
1376             }
1377         }
1378       else
1379         {
1380           /* Copy a single element.  */
1381           bitmap_element *src;
1382
1383           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
1384             {
1385               src = a_elt;
1386               a_elt = a_elt->next;
1387             }
1388           else
1389             {
1390               src = b_elt;
1391               b_elt = b_elt->next;
1392             }
1393
1394           if (!dst_elt)
1395             dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
1396           else
1397             dst_elt->indx = src->indx;
1398           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
1399           dst_prev = dst_elt;
1400           dst_elt = dst_elt->next;
1401         }
1402     }
1403   /* Ensure that dst->current is valid.  */
1404   dst->current = dst->first;
1405   bitmap_elt_clear_from (dst, dst_elt);
1406   gcc_assert (!dst->current == !dst->first);
1407   if (dst->current)
1408     dst->indx = dst->current->indx;
1409 }
1410
1411 /* A ^= B */
1412
1413 void
1414 bitmap_xor_into (bitmap a, bitmap b)
1415 {
1416   bitmap_element *a_elt = a->first;
1417   bitmap_element *b_elt = b->first;
1418   bitmap_element *a_prev = NULL;
1419
1420   if (a == b)
1421     {
1422       bitmap_clear (a);
1423       return;
1424     }
1425
1426   while (b_elt)
1427     {
1428       if (!a_elt || b_elt->indx < a_elt->indx)
1429         {
1430           /* Copy b_elt.  */
1431           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
1432           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1433           a_prev = dst;
1434           b_elt = b_elt->next;
1435         }
1436       else if (a_elt->indx < b_elt->indx)
1437         {
1438           a_prev = a_elt;
1439           a_elt = a_elt->next;
1440         }
1441       else
1442         {
1443           /* Matching elts, generate A ^= B.  */
1444           unsigned ix;
1445           BITMAP_WORD ior = 0;
1446           bitmap_element *next = a_elt->next;
1447
1448           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1449             {
1450               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1451
1452               ior |= r;
1453               a_elt->bits[ix] = r;
1454             }
1455           b_elt = b_elt->next;
1456           if (ior)
1457             a_prev = a_elt;
1458           else
1459             bitmap_element_free (a, a_elt);
1460           a_elt = next;
1461         }
1462     }
1463   gcc_assert (!a->current == !a->first);
1464   if (a->current)
1465     a->indx = a->current->indx;
1466 }
1467
1468 /* Return true if two bitmaps are identical.
1469    We do not bother with a check for pointer equality, as that never
1470    occurs in practice.  */
1471
1472 bool
1473 bitmap_equal_p (bitmap a, bitmap b)
1474 {
1475   bitmap_element *a_elt;
1476   bitmap_element *b_elt;
1477   unsigned ix;
1478
1479   for (a_elt = a->first, b_elt = b->first;
1480        a_elt && b_elt;
1481        a_elt = a_elt->next, b_elt = b_elt->next)
1482     {
1483       if (a_elt->indx != b_elt->indx)
1484         return false;
1485       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1486         if (a_elt->bits[ix] != b_elt->bits[ix])
1487           return false;
1488     }
1489   return !a_elt && !b_elt;
1490 }
1491
1492 /* Return true if A AND B is not empty.  */
1493
1494 bool
1495 bitmap_intersect_p (bitmap a, bitmap b)
1496 {
1497   bitmap_element *a_elt;
1498   bitmap_element *b_elt;
1499   unsigned ix;
1500
1501   for (a_elt = a->first, b_elt = b->first;
1502        a_elt && b_elt;)
1503     {
1504       if (a_elt->indx < b_elt->indx)
1505         a_elt = a_elt->next;
1506       else if (b_elt->indx < a_elt->indx)
1507         b_elt = b_elt->next;
1508       else
1509         {
1510           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1511             if (a_elt->bits[ix] & b_elt->bits[ix])
1512               return true;
1513           a_elt = a_elt->next;
1514           b_elt = b_elt->next;
1515         }
1516     }
1517   return false;
1518 }
1519
1520 /* Return true if A AND NOT B is not empty.  */
1521
1522 bool
1523 bitmap_intersect_compl_p (bitmap a, bitmap b)
1524 {
1525   bitmap_element *a_elt;
1526   bitmap_element *b_elt;
1527   unsigned ix;
1528   for (a_elt = a->first, b_elt = b->first;
1529        a_elt && b_elt;)
1530     {
1531       if (a_elt->indx < b_elt->indx)
1532         return true;
1533       else if (b_elt->indx < a_elt->indx)
1534         b_elt = b_elt->next;
1535       else
1536         {
1537           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1538             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1539               return true;
1540           a_elt = a_elt->next;
1541           b_elt = b_elt->next;
1542         }
1543     }
1544   return a_elt != NULL;
1545 }
1546
1547 \f
1548 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1549
1550 bool
1551 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1552 {
1553   bitmap_head tmp;
1554   bool changed;
1555
1556   bitmap_initialize (&tmp, &bitmap_default_obstack);
1557   bitmap_and_compl (&tmp, from1, from2);
1558   changed = bitmap_ior (dst, a, &tmp);
1559   bitmap_clear (&tmp);
1560
1561   return changed;
1562 }
1563
1564 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1565
1566 bool
1567 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1568 {
1569   bitmap_head tmp;
1570   bool changed;
1571
1572   bitmap_initialize (&tmp, &bitmap_default_obstack);
1573   bitmap_and_compl (&tmp, from1, from2);
1574   changed = bitmap_ior_into (a, &tmp);
1575   bitmap_clear (&tmp);
1576
1577   return changed;
1578 }
1579 \f
1580 /* Debugging function to print out the contents of a bitmap.  */
1581
1582 void
1583 debug_bitmap_file (FILE *file, bitmap head)
1584 {
1585   bitmap_element *ptr;
1586
1587   fprintf (file, "\nfirst = %p current = %p indx = %u\n",
1588            (void *) head->first, (void *) head->current, head->indx);
1589
1590   for (ptr = head->first; ptr; ptr = ptr->next)
1591     {
1592       unsigned int i, j, col = 26;
1593
1594       fprintf (file, "\t%p next = %p prev = %p indx = %u\n\t\tbits = {",
1595                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1596
1597       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1598         for (j = 0; j < BITMAP_WORD_BITS; j++)
1599           if ((ptr->bits[i] >> j) & 1)
1600             {
1601               if (col > 70)
1602                 {
1603                   fprintf (file, "\n\t\t\t");
1604                   col = 24;
1605                 }
1606
1607               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1608                                      + i * BITMAP_WORD_BITS + j));
1609               col += 4;
1610             }
1611
1612       fprintf (file, " }\n");
1613     }
1614 }
1615
1616 /* Function to be called from the debugger to print the contents
1617    of a bitmap.  */
1618
1619 void
1620 debug_bitmap (bitmap head)
1621 {
1622   debug_bitmap_file (stdout, head);
1623 }
1624
1625 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1626    it does not print anything but the bits.  */
1627
1628 void
1629 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1630 {
1631   const char *comma = "";
1632   unsigned i;
1633   bitmap_iterator bi;
1634
1635   fputs (prefix, file);
1636   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1637     {
1638       fprintf (file, "%s%d", comma, i);
1639       comma = ", ";
1640     }
1641   fputs (suffix, file);
1642 }
1643 #ifdef GATHER_STATISTICS
1644
1645
1646 /* Used to accumulate statistics about bitmap sizes.  */
1647 struct output_info
1648 {
1649   int count;
1650   int size;
1651 };
1652
1653 /* Called via htab_traverse.  Output bitmap descriptor pointed out by SLOT
1654    and update statistics.  */
1655 static int
1656 print_statistics (void **slot, void *b)
1657 {
1658   struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
1659   struct output_info *i = (struct output_info *) b;
1660   char s[4096];
1661
1662   if (d->allocated)
1663     {
1664       const char *s1 = d->file;
1665       const char *s2;
1666       while ((s2 = strstr (s1, "gcc/")))
1667         s1 = s2 + 4;
1668       sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
1669       s[41] = 0;
1670       fprintf (stderr, "%-41s %6d %10d %10d %10d %10d\n", s,
1671                d->created, d->allocated, d->peak, d->current, d->nsearches);
1672       i->size += d->allocated;
1673       i->count += d->created;
1674     }
1675   return 1;
1676 }
1677 #endif
1678 /* Output per-bitmap memory usage statistics.  */
1679 void
1680 dump_bitmap_statistics (void)
1681 {
1682 #ifdef GATHER_STATISTICS
1683   struct output_info info;
1684
1685   if (!bitmap_desc_hash)
1686     return;
1687
1688   fprintf (stderr, "\nBitmap                                     Overall "
1689                    "Allocated     Peak        Leak   searched "
1690                    "  per search\n");
1691   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1692   info.count = 0;
1693   info.size = 0;
1694   htab_traverse (bitmap_desc_hash, print_statistics, &info);
1695   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1696   fprintf (stderr, "%-40s %7d %10d\n",
1697            "Total", info.count, info.size);
1698   fprintf (stderr, "---------------------------------------------------------------------------------\n");
1699 #endif
1700 }
1701
1702 /* Compute hash of bitmap (for purposes of hashing).  */
1703 hashval_t
1704 bitmap_hash (bitmap head)
1705 {
1706   bitmap_element *ptr;
1707   BITMAP_WORD hash = 0;
1708   int ix;
1709
1710   for (ptr = head->first; ptr; ptr = ptr->next)
1711     {
1712       hash ^= ptr->indx;
1713       for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
1714         hash ^= ptr->bits[ix];
1715     }
1716   return (hashval_t)hash;
1717 }
1718
1719 #include "gt-bitmap.h"