gcc/bitmap.c

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