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