gcc/bitmap.c

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