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