gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "obstack.h"
  29 #include "ggc.h"
  30 #include "bitmap.h"
  31
  32 /* Obstack to allocate bitmap elements from.  */
  33 \f
  34 #ifndef INLINE
  35 #ifndef __GNUC__
  36 #define INLINE
  37 #else
  38 #define INLINE __inline__
  39 #endif
  40 #endif
  41
  42 /* Global data */
  43 bitmap_element bitmap_zero_bits;  /* An element of all zero bits.  */
  44 bitmap_obstack bitmap_default_obstack;    /* The default bitmap obstack.  */
  45 static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of
  46                                                             GC'd elements.  */
  47
  48 static void bitmap_elem_to_freelist (bitmap, bitmap_element *);
  49 static void bitmap_element_free (bitmap, bitmap_element *);
  50 static bitmap_element *bitmap_element_allocate (bitmap);
  51 static int bitmap_element_zerop (bitmap_element *);
  52 static void bitmap_element_link (bitmap, bitmap_element *);
  53 static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *);
  54 static void bitmap_elt_clear_from (bitmap, bitmap_element *);
  55 static bitmap_element *bitmap_find_bit (bitmap, unsigned int);
  56 \f
  57
  58 /* Add ELEM to the appropriate freelist.  */
  59 static INLINE void
  60 bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
  61 {
  62   bitmap_obstack *bit_obstack = head->obstack;
  63
  64   if (bit_obstack)
  65     {
  66       elt->next = bit_obstack->elements;
  67       bit_obstack->elements = elt;
  68     }
  69   else
  70     {
  71       elt->next = bitmap_ggc_free;
  72       bitmap_ggc_free = elt;
  73     }
  74 }
  75
  76 /* Free a bitmap element.  Since these are allocated off the
  77    bitmap_obstack, "free" actually means "put onto the freelist".  */
  78
  79 static INLINE void
  80 bitmap_element_free (bitmap head, bitmap_element *elt)
  81 {
  82   bitmap_element *next = elt->next;
  83   bitmap_element *prev = elt->prev;
  84
  85   if (prev)
  86     prev->next = next;
  87
  88   if (next)
  89     next->prev = prev;
  90
  91   if (head->first == elt)
  92     head->first = next;
  93
  94   /* Since the first thing we try is to insert before current,
  95      make current the next entry in preference to the previous.  */
  96   if (head->current == elt)
  97     {
  98       head->current = next != 0 ? next : prev;
  99       if (head->current)
 100         head->indx = head->current->indx;
 101     }
 102   bitmap_elem_to_freelist (head, elt);
 103 }
 104 \f
 105 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 106
 107 static INLINE bitmap_element *
 108 bitmap_element_allocate (bitmap head)
 109 {
 110   bitmap_element *element;
 111   bitmap_obstack *bit_obstack = head->obstack;
 112
 113   if (bit_obstack)
 114     {
 115       element = bit_obstack->elements;
 116
 117       if (element)
 118         bit_obstack->elements = element->next;
 119       else
 120         element = XOBNEW (&bit_obstack->obstack, bitmap_element);
 121     }
 122   else
 123     {
 124       element = bitmap_ggc_free;
 125       if (element)
 126         bitmap_ggc_free = element->next;
 127       else
 128         element = GGC_NEW (bitmap_element);
 129     }
 130
 131   memset (element->bits, 0, sizeof (element->bits));
 132
 133   return element;
 134 }
 135
 136 /* Remove ELT and all following elements from bitmap HEAD.  */
 137
 138 void
 139 bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
 140 {
 141   bitmap_element *next;
 142
 143   while (elt)
 144     {
 145       next = elt->next;
 146       bitmap_element_free (head, elt);
 147       elt = next;
 148     }
 149 }
 150
 151 /* Clear a bitmap by freeing the linked list.  */
 152
 153 INLINE void
 154 bitmap_clear (bitmap head)
 155 {
 156   bitmap_element *element, *next;
 157
 158   for (element = head->first; element != 0; element = next)
 159     {
 160       next = element->next;
 161       bitmap_elem_to_freelist (head, element);
 162     }
 163
 164   head->first = head->current = 0;
 165 }
 166 \f
 167 /* Initialize a bitmap obstack.  If BIT_OBSTACK is NULL, initialize
 168    the default bitmap obstack.  */
 169
 170 void
 171 bitmap_obstack_initialize (bitmap_obstack *bit_obstack)
 172 {
 173   if (!bit_obstack)
 174     bit_obstack = &bitmap_default_obstack;
 175
 176 #if !defined(__GNUC__) || (__GNUC__ < 2)
 177 #define __alignof__(type) 0
 178 #endif
 179
 180   bit_obstack->elements = NULL;
 181   bit_obstack->heads = NULL;
 182   obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE,
 183                               __alignof__ (bitmap_element),
 184                               obstack_chunk_alloc,
 185                               obstack_chunk_free);
 186 }
 187
 188 /* Release the memory from a bitmap obstack.  If BIT_OBSTACK is NULL,
 189    release the default bitmap obstack.  */
 190
 191 void
 192 bitmap_obstack_release (bitmap_obstack *bit_obstack)
 193 {
 194   if (!bit_obstack)
 195     bit_obstack = &bitmap_default_obstack;
 196
 197   bit_obstack->elements = NULL;
 198   bit_obstack->heads = NULL;
 199   obstack_free (&bit_obstack->obstack, NULL);
 200 }
 201
 202 /* Create a new bitmap on an obstack.  If BIT_OBSTACK is NULL, create
 203    it on the default bitmap obstack.  */
 204
 205 bitmap
 206 bitmap_obstack_alloc (bitmap_obstack *bit_obstack)
 207 {
 208   bitmap map;
 209
 210   if (!bit_obstack)
 211     bit_obstack = &bitmap_default_obstack;
 212   map = bit_obstack->heads;
 213   if (map)
 214     bit_obstack->heads = (void *)map->first;
 215   else
 216     map = XOBNEW (&bit_obstack->obstack, bitmap_head);
 217   bitmap_initialize (map, bit_obstack);
 218
 219   return map;
 220 }
 221
 222 /* Create a new GCd bitmap.  */
 223
 224 bitmap
 225 bitmap_gc_alloc (void)
 226 {
 227   bitmap map;
 228
 229   map = GGC_NEW (struct bitmap_head_def);
 230   bitmap_initialize (map, NULL);
 231
 232   return map;
 233 }
 234
 235 /* Create a new malloced bitmap.  Elements will be allocated from the
 236    default bitmap obstack.  */
 237
 238 bitmap
 239 bitmap_malloc_alloc (void)
 240 {
 241   bitmap map;
 242
 243   map = xmalloc (sizeof (bitmap_head));
 244   bitmap_initialize (map, &bitmap_default_obstack);
 245
 246   return map;
 247 }
 248
 249 /* Release an obstack allocated bitmap.  */
 250
 251 void
 252 bitmap_obstack_free (bitmap map)
 253 {
 254   bitmap_clear (map);
 255   map->first = (void *)map->obstack->heads;
 256   map->obstack->heads = map;
 257 }
 258
 259 /* Release a malloc allocated bitmap.  */
 260
 261 void
 262 bitmap_malloc_free (bitmap map)
 263 {
 264   bitmap_clear (map);
 265   free (map);
 266 }
 267
 268 \f
 269 /* Return nonzero if all bits in an element are zero.  */
 270
 271 static INLINE int
 272 bitmap_element_zerop (bitmap_element *element)
 273 {
 274 #if BITMAP_ELEMENT_WORDS == 2
 275   return (element->bits[0] | element->bits[1]) == 0;
 276 #else
 277   unsigned i;
 278
 279   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 280     if (element->bits[i] != 0)
 281       return 0;
 282
 283   return 1;
 284 #endif
 285 }
 286 \f
 287 /* Link the bitmap element into the current bitmap linked list.  */
 288
 289 static INLINE void
 290 bitmap_element_link (bitmap head, bitmap_element *element)
 291 {
 292   unsigned int indx = element->indx;
 293   bitmap_element *ptr;
 294
 295   /* If this is the first and only element, set it in.  */
 296   if (head->first == 0)
 297     {
 298       element->next = element->prev = 0;
 299       head->first = element;
 300     }
 301
 302   /* If this index is less than that of the current element, it goes someplace
 303      before the current element.  */
 304   else if (indx < head->indx)
 305     {
 306       for (ptr = head->current;
 307            ptr->prev != 0 && ptr->prev->indx > indx;
 308            ptr = ptr->prev)
 309         ;
 310
 311       if (ptr->prev)
 312         ptr->prev->next = element;
 313       else
 314         head->first = element;
 315
 316       element->prev = ptr->prev;
 317       element->next = ptr;
 318       ptr->prev = element;
 319     }
 320
 321   /* Otherwise, it must go someplace after the current element.  */
 322   else
 323     {
 324       for (ptr = head->current;
 325            ptr->next != 0 && ptr->next->indx < indx;
 326            ptr = ptr->next)
 327         ;
 328
 329       if (ptr->next)
 330         ptr->next->prev = element;
 331
 332       element->next = ptr->next;
 333       element->prev = ptr;
 334       ptr->next = element;
 335     }
 336
 337   /* Set up so this is the first element searched.  */
 338   head->current = element;
 339   head->indx = indx;
 340 }
 341
 342 /* Insert a new uninitialized element into bitmap HEAD after element
 343    ELT.  If ELT is NULL, insert the element at the start.  Return the
 344    new element.  */
 345
 346 static bitmap_element *
 347 bitmap_elt_insert_after (bitmap head, bitmap_element *elt)
 348 {
 349   bitmap_element *node = bitmap_element_allocate (head);
 350
 351   if (!elt)
 352     {
 353       if (!head->current)
 354         head->current = node;
 355       node->next = head->first;
 356       if (node->next)
 357         node->next->prev = node;
 358       head->first = node;
 359       node->prev = NULL;
 360     }
 361   else
 362     {
 363       gcc_assert (head->current);
 364       node->next = elt->next;
 365       if (node->next)
 366         node->next->prev = node;
 367       elt->next = node;
 368       node->prev = elt;
 369     }
 370   return node;
 371 }
 372 \f
 373 /* Copy a bitmap to another bitmap.  */
 374
 375 void
 376 bitmap_copy (bitmap to, bitmap from)
 377 {
 378   bitmap_element *from_ptr, *to_ptr = 0;
 379 #if BITMAP_ELEMENT_WORDS != 2
 380   unsigned i;
 381 #endif
 382
 383   bitmap_clear (to);
 384
 385   /* Copy elements in forward direction one at a time.  */
 386   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 387     {
 388       bitmap_element *to_elt = bitmap_element_allocate (to);
 389
 390       to_elt->indx = from_ptr->indx;
 391
 392 #if BITMAP_ELEMENT_WORDS == 2
 393       to_elt->bits[0] = from_ptr->bits[0];
 394       to_elt->bits[1] = from_ptr->bits[1];
 395 #else
 396       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 397         to_elt->bits[i] = from_ptr->bits[i];
 398 #endif
 399
 400       /* Here we have a special case of bitmap_element_link, for the case
 401          where we know the links are being entered in sequence.  */
 402       if (to_ptr == 0)
 403         {
 404           to->first = to->current = to_elt;
 405           to->indx = from_ptr->indx;
 406           to_elt->next = to_elt->prev = 0;
 407         }
 408       else
 409         {
 410           to_elt->prev = to_ptr;
 411           to_elt->next = 0;
 412           to_ptr->next = to_elt;
 413         }
 414
 415       to_ptr = to_elt;
 416     }
 417 }
 418 \f
 419 /* Find a bitmap element that would hold a bitmap's bit.
 420    Update the `current' field even if we can't find an element that
 421    would hold the bitmap's bit to make eventual allocation
 422    faster.  */
 423
 424 static INLINE bitmap_element *
 425 bitmap_find_bit (bitmap head, unsigned int bit)
 426 {
 427   bitmap_element *element;
 428   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 429
 430   if (head->current == 0
 431       || head->indx == indx)
 432     return head->current;
 433
 434   if (head->indx > indx)
 435     for (element = head->current;
 436          element->prev != 0 && element->indx > indx;
 437          element = element->prev)
 438       ;
 439
 440   else
 441     for (element = head->current;
 442          element->next != 0 && element->indx < indx;
 443          element = element->next)
 444       ;
 445
 446   /* `element' is the nearest to the one we want.  If it's not the one we
 447      want, the one we want doesn't exist.  */
 448   head->current = element;
 449   head->indx = element->indx;
 450   if (element != 0 && element->indx != indx)
 451     element = 0;
 452
 453   return element;
 454 }
 455 \f
 456 /* Clear a single bit in a bitmap.  */
 457
 458 void
 459 bitmap_clear_bit (bitmap head, int bit)
 460 {
 461   bitmap_element *ptr = bitmap_find_bit (head, bit);
 462
 463   if (ptr != 0)
 464     {
 465       unsigned bit_num  = bit % BITMAP_WORD_BITS;
 466       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 467       ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
 468
 469       /* If we cleared the entire word, free up the element.  */
 470       if (bitmap_element_zerop (ptr))
 471         bitmap_element_free (head, ptr);
 472     }
 473 }
 474
 475 /* Set a single bit in a bitmap.  */
 476
 477 void
 478 bitmap_set_bit (bitmap head, int bit)
 479 {
 480   bitmap_element *ptr = bitmap_find_bit (head, bit);
 481   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 482   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 483   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 484
 485   if (ptr == 0)
 486     {
 487       ptr = bitmap_element_allocate (head);
 488       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 489       ptr->bits[word_num] = bit_val;
 490       bitmap_element_link (head, ptr);
 491     }
 492   else
 493     ptr->bits[word_num] |= bit_val;
 494 }
 495
 496 /* Return whether a bit is set within a bitmap.  */
 497
 498 int
 499 bitmap_bit_p (bitmap head, int bit)
 500 {
 501   bitmap_element *ptr;
 502   unsigned bit_num;
 503   unsigned word_num;
 504
 505   ptr = bitmap_find_bit (head, bit);
 506   if (ptr == 0)
 507     return 0;
 508
 509   bit_num = bit % BITMAP_WORD_BITS;
 510   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 511
 512   return (ptr->bits[word_num] >> bit_num) & 1;
 513 }
 514 \f
 515 /* Return the bit number of the first set bit in the bitmap.  The
 516    bitmap must be non-empty.  */
 517
 518 unsigned
 519 bitmap_first_set_bit (bitmap a)
 520 {
 521   bitmap_element *elt = a->first;
 522   unsigned bit_no;
 523   BITMAP_WORD word;
 524   unsigned ix;
 525
 526   gcc_assert (elt);
 527   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 528   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 529     {
 530       word = elt->bits[ix];
 531       if (word)
 532         goto found_bit;
 533     }
 534   gcc_unreachable ();
 535  found_bit:
 536   bit_no += ix * BITMAP_WORD_BITS;
 537
 538 #if GCC_VERSION >= 3004
 539   gcc_assert (sizeof(long) == sizeof (word));
 540   bit_no += __builtin_ctzl (word);
 541 #else
 542   /* Binary search for the first set bit.  */
 543 #if BITMAP_WORD_BITS > 64
 544 #error "Fill out the table."
 545 #endif
 546 #if BITMAP_WORD_BITS > 32
 547   if (!(word & 0xffffffff))
 548     word >>= 32, bit_no += 32;
 549 #endif
 550   if (!(word & 0xffff))
 551     word >>= 16, bit_no += 16;
 552   if (!(word & 0xff))
 553     word >>= 8, bit_no += 8;
 554   if (!(word & 0xf))
 555     word >>= 4, bit_no += 4;
 556   if (!(word & 0x3))
 557     word >>= 2, bit_no += 2;
 558   if (!(word & 0x1))
 559     word >>= 1, bit_no += 1;
 560
 561  gcc_assert (word & 1);
 562 #endif
 563  return bit_no;
 564 }
 565 \f
 566
 567 /* DST = A & B.  */
 568
 569 void
 570 bitmap_and (bitmap dst, bitmap a, bitmap b)
 571 {
 572   bitmap_element *dst_elt = dst->first;
 573   bitmap_element *a_elt = a->first;
 574   bitmap_element *b_elt = b->first;
 575   bitmap_element *dst_prev = NULL;
 576
 577   gcc_assert (dst != a && dst != b && a != b);
 578   while (a_elt && b_elt)
 579     {
 580       if (a_elt->indx < b_elt->indx)
 581         a_elt = a_elt->next;
 582       else if (b_elt->indx < a_elt->indx)
 583         b_elt = b_elt->next;
 584       else
 585         {
 586           /* Matching elts, generate A & B.  */
 587           unsigned ix;
 588           BITMAP_WORD ior = 0;
 589
 590           if (!dst_elt)
 591             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 592
 593           dst_elt->indx = a_elt->indx;
 594           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 595             {
 596               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 597
 598               dst_elt->bits[ix] = r;
 599               ior |= r;
 600             }
 601           if (ior)
 602             {
 603               dst_prev = dst_elt;
 604               dst_elt = dst_elt->next;
 605             }
 606           a_elt = a_elt->next;
 607           b_elt = b_elt->next;
 608         }
 609     }
 610   bitmap_elt_clear_from (dst, dst_elt);
 611   gcc_assert (!dst->current == !dst->first);
 612   if (dst->current)
 613     dst->indx = dst->current->indx;
 614 }
 615
 616 /* A &= B.  */
 617
 618 void
 619 bitmap_and_into (bitmap a, bitmap b)
 620 {
 621   bitmap_element *a_elt = a->first;
 622   bitmap_element *b_elt = b->first;
 623   bitmap_element *next;
 624
 625   gcc_assert (a != b);
 626   while (a_elt && b_elt)
 627     {
 628       if (a_elt->indx < b_elt->indx)
 629         {
 630           next = a_elt->next;
 631           bitmap_element_free (a, a_elt);
 632           a_elt = next;
 633         }
 634       else if (b_elt->indx < a_elt->indx)
 635         b_elt = b_elt->next;
 636       else
 637         {
 638           /* Matching elts, generate A &= B.  */
 639           unsigned ix;
 640           BITMAP_WORD ior = 0;
 641
 642           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 643             {
 644               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 645
 646               a_elt->bits[ix] = r;
 647               ior |= r;
 648             }
 649           next = a_elt->next;
 650           if (!ior)
 651             bitmap_element_free (a, a_elt);
 652           a_elt = next;
 653           b_elt = b_elt->next;
 654         }
 655     }
 656   bitmap_elt_clear_from (a, a_elt);
 657   gcc_assert (!a->current == !a->first);
 658   gcc_assert (!a->current || a->indx == a->current->indx);
 659 }
 660
 661 /* DST = A & ~B  */
 662
 663 void
 664 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 665 {
 666   bitmap_element *dst_elt = dst->first;
 667   bitmap_element *a_elt = a->first;
 668   bitmap_element *b_elt = b->first;
 669   bitmap_element *dst_prev = NULL;
 670
 671   gcc_assert (dst != a && dst != b && a != b);
 672
 673   while (a_elt)
 674     {
 675       if (!b_elt || a_elt->indx < b_elt->indx)
 676         {
 677           /* Copy a_elt.  */
 678           if (!dst_elt)
 679             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 680
 681           dst_elt->indx = a_elt->indx;
 682           memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 683           dst_prev = dst_elt;
 684           dst_elt = dst_elt->next;
 685           a_elt = a_elt->next;
 686         }
 687       else if (b_elt->indx < a_elt->indx)
 688         b_elt = b_elt->next;
 689       else
 690         {
 691           /* Matching elts, generate A & ~B.  */
 692           unsigned ix;
 693           BITMAP_WORD ior = 0;
 694
 695           if (!dst_elt)
 696             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 697
 698           dst_elt->indx = a_elt->indx;
 699           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 700             {
 701               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 702
 703               dst_elt->bits[ix] = r;
 704               ior |= r;
 705             }
 706           if (ior)
 707             {
 708               dst_prev = dst_elt;
 709               dst_elt = dst_elt->next;
 710             }
 711           a_elt = a_elt->next;
 712           b_elt = b_elt->next;
 713         }
 714     }
 715   bitmap_elt_clear_from (dst, dst_elt);
 716   gcc_assert (!dst->current == !dst->first);
 717   if (dst->current)
 718     dst->indx = dst->current->indx;
 719 }
 720
 721 /* A &= ~B */
 722
 723 void
 724 bitmap_and_compl_into (bitmap a, bitmap b)
 725 {
 726   bitmap_element *a_elt = a->first;
 727   bitmap_element *b_elt = b->first;
 728   bitmap_element *next;
 729
 730   gcc_assert (a != b);
 731   while (a_elt && b_elt)
 732     {
 733       if (a_elt->indx < b_elt->indx)
 734         a_elt = a_elt->next;
 735       else if (b_elt->indx < a_elt->indx)
 736         b_elt = b_elt->next;
 737       else
 738         {
 739           /* Matching elts, generate A &= ~B.  */
 740           unsigned ix;
 741           BITMAP_WORD ior = 0;
 742
 743           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 744             {
 745               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 746
 747               a_elt->bits[ix] = r;
 748               ior |= r;
 749             }
 750           next = a_elt->next;
 751           if (!ior)
 752             bitmap_element_free (a, a_elt);
 753           a_elt = next;
 754           b_elt = b_elt->next;
 755         }
 756     }
 757   gcc_assert (!a->current == !a->first);
 758   gcc_assert (!a->current || a->indx == a->current->indx);
 759 }
 760
 761 /* DST = A | B.  Return true if DST changes.  */
 762
 763 bool
 764 bitmap_ior (bitmap dst, bitmap a, bitmap b)
 765 {
 766   bitmap_element *dst_elt = dst->first;
 767   bitmap_element *a_elt = a->first;
 768   bitmap_element *b_elt = b->first;
 769   bitmap_element *dst_prev = NULL;
 770   bool changed = false;
 771
 772   gcc_assert (dst != a && dst != b && a != b);
 773   while (a_elt || b_elt)
 774     {
 775       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 776         {
 777           /* Matching elts, generate A | B.  */
 778           unsigned ix;
 779
 780           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
 781             {
 782               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 783                 {
 784                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 785
 786                   if (r != dst_elt->bits[ix])
 787                     {
 788                       dst_elt->bits[ix] = r;
 789                       changed = true;
 790                     }
 791                 }
 792             }
 793           else
 794             {
 795               changed = true;
 796               if (!dst_elt)
 797                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 798               dst_elt->indx = a_elt->indx;
 799               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 800                 {
 801                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 802
 803                   dst_elt->bits[ix] = r;
 804                 }
 805             }
 806           a_elt = a_elt->next;
 807           b_elt = b_elt->next;
 808           dst_prev = dst_elt;
 809           dst_elt = dst_elt->next;
 810         }
 811       else
 812         {
 813           /* Copy a single element.  */
 814           bitmap_element *src;
 815
 816           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 817             {
 818               src = a_elt;
 819               a_elt = a_elt->next;
 820             }
 821           else
 822             {
 823               src = b_elt;
 824               b_elt = b_elt->next;
 825             }
 826
 827           if (!changed && dst_elt && dst_elt->indx == src->indx)
 828             {
 829               unsigned ix;
 830
 831               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 832                 if (src->bits[ix] != dst_elt->bits[ix])
 833                   {
 834                     dst_elt->bits[ix] = src->bits[ix];
 835                     changed = true;
 836                   }
 837             }
 838           else
 839             {
 840               changed = true;
 841               if (!dst_elt)
 842                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 843               dst_elt->indx = src->indx;
 844               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 845             }
 846
 847           dst_prev = dst_elt;
 848           dst_elt = dst_elt->next;
 849         }
 850     }
 851
 852   if (dst_elt)
 853     {
 854       changed = true;
 855       bitmap_elt_clear_from (dst, dst_elt);
 856     }
 857   gcc_assert (!dst->current == !dst->first);
 858   if (dst->current)
 859     dst->indx = dst->current->indx;
 860   return changed;
 861 }
 862
 863 /* A |= B.  Return true if A changes.  */
 864
 865 bool
 866 bitmap_ior_into (bitmap a, bitmap b)
 867 {
 868   bitmap_element *a_elt = a->first;
 869   bitmap_element *b_elt = b->first;
 870   bitmap_element *a_prev = NULL;
 871   bool changed = false;
 872
 873   gcc_assert (a != b);
 874   while (b_elt)
 875     {
 876       if (!a_elt || b_elt->indx < a_elt->indx)
 877         {
 878           /* Copy b_elt.  */
 879           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 880
 881           dst->indx = b_elt->indx;
 882           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 883           a_prev = dst;
 884           b_elt = b_elt->next;
 885           changed = true;
 886         }
 887       else if (a_elt->indx < b_elt->indx)
 888         {
 889           a_prev = a_elt;
 890           a_elt = a_elt->next;
 891         }
 892       else
 893         {
 894           /* Matching elts, generate A |= B.  */
 895           unsigned ix;
 896
 897           if (changed)
 898             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 899               {
 900                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 901
 902                 a_elt->bits[ix] = r;
 903               }
 904           else
 905             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 906               {
 907                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 908
 909                 if (a_elt->bits[ix] != r)
 910                   {
 911                     changed = true;
 912                     a_elt->bits[ix] = r;
 913                   }
 914               }
 915           b_elt = b_elt->next;
 916           a_prev = a_elt;
 917           a_elt = a_elt->next;
 918         }
 919     }
 920   gcc_assert (!a->current == !a->first);
 921   if (a->current)
 922     a->indx = a->current->indx;
 923   return changed;
 924 }
 925
 926 /* DST = A ^ B  */
 927
 928 void
 929 bitmap_xor (bitmap dst, bitmap a, bitmap b)
 930 {
 931   bitmap_element *dst_elt = dst->first;
 932   bitmap_element *a_elt = a->first;
 933   bitmap_element *b_elt = b->first;
 934   bitmap_element *dst_prev = NULL;
 935
 936   gcc_assert (dst != a && dst != b && a != b);
 937   while (a_elt || b_elt)
 938     {
 939       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 940         {
 941           /* Matching elts, generate A ^ B.  */
 942           unsigned ix;
 943           BITMAP_WORD ior = 0;
 944
 945           if (!dst_elt)
 946             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 947
 948           dst_elt->indx = a_elt->indx;
 949           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 950             {
 951               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
 952
 953               ior |= r;
 954               dst_elt->bits[ix] = r;
 955             }
 956           a_elt = a_elt->next;
 957           b_elt = b_elt->next;
 958           if (ior)
 959             {
 960               dst_prev = dst_elt;
 961               dst_elt = dst_elt->next;
 962             }
 963         }
 964       else
 965         {
 966           /* Copy a single element.  */
 967           bitmap_element *src;
 968
 969           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 970             {
 971               src = a_elt;
 972               a_elt = a_elt->next;
 973             }
 974           else
 975             {
 976               src = b_elt;
 977               b_elt = b_elt->next;
 978             }
 979
 980           if (!dst_elt)
 981             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 982
 983           dst_elt->indx = src->indx;
 984           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 985           dst_prev = dst_elt;
 986           dst_elt = dst_elt->next;
 987         }
 988     }
 989   bitmap_elt_clear_from (dst, dst_elt);
 990   gcc_assert (!dst->current == !dst->first);
 991   if (dst->current)
 992     dst->indx = dst->current->indx;
 993 }
 994
 995 /* A ^= B */
 996
 997 void
 998 bitmap_xor_into (bitmap a, bitmap b)
 999 {
1000   bitmap_element *a_elt = a->first;
1001   bitmap_element *b_elt = b->first;
1002   bitmap_element *a_prev = NULL;
1003
1004   gcc_assert (a != b);
1005   while (b_elt)
1006     {
1007       if (!a_elt || b_elt->indx < a_elt->indx)
1008         {
1009           /* Copy b_elt.  */
1010           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
1011
1012           dst->indx = b_elt->indx;
1013           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1014           a_prev = dst;
1015           b_elt = b_elt->next;
1016         }
1017       else if (a_elt->indx < b_elt->indx)
1018         {
1019           a_prev = a_elt;
1020           a_elt = a_elt->next;
1021         }
1022       else
1023         {
1024           /* Matching elts, generate A ^= B.  */
1025           unsigned ix;
1026           BITMAP_WORD ior = 0;
1027           bitmap_element *next = a_elt->next;
1028
1029           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1030             {
1031               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1032
1033               ior |= r;
1034               a_elt->bits[ix] = r;
1035             }
1036           b_elt = b_elt->next;
1037           if (ior)
1038             a_prev = a_elt;
1039           else
1040             bitmap_element_free (a, a_elt);
1041           a_elt = next;
1042         }
1043     }
1044   gcc_assert (!a->current == !a->first);
1045   if (a->current)
1046     a->indx = a->current->indx;
1047 }
1048
1049 /* Return true if two bitmaps are identical.
1050    We do not bother with a check for pointer equality, as that never
1051    occurs in practice.  */
1052
1053 bool
1054 bitmap_equal_p (bitmap a, bitmap b)
1055 {
1056   bitmap_element *a_elt;
1057   bitmap_element *b_elt;
1058   unsigned ix;
1059
1060   for (a_elt = a->first, b_elt = b->first;
1061        a_elt && b_elt;
1062        a_elt = a_elt->next, b_elt = b_elt->next)
1063     {
1064       if (a_elt->indx != b_elt->indx)
1065         return false;
1066       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1067         if (a_elt->bits[ix] != b_elt->bits[ix])
1068           return false;
1069     }
1070   return !a_elt && !b_elt;
1071 }
1072
1073 /* Return true if A AND B is not empty.  */
1074
1075 bool
1076 bitmap_intersect_p (bitmap a, bitmap b)
1077 {
1078   bitmap_element *a_elt;
1079   bitmap_element *b_elt;
1080   unsigned ix;
1081
1082   for (a_elt = a->first, b_elt = b->first;
1083        a_elt && b_elt;)
1084     {
1085       if (a_elt->indx < b_elt->indx)
1086         a_elt = a_elt->next;
1087       else if (b_elt->indx < a_elt->indx)
1088         b_elt = b_elt->next;
1089       else
1090         {
1091           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1092             if (a_elt->bits[ix] & b_elt->bits[ix])
1093               return true;
1094           a_elt = a_elt->next;
1095           b_elt = b_elt->next;
1096         }
1097     }
1098   return false;
1099 }
1100
1101 /* Return true if A AND NOT B is not empty.  */
1102
1103 bool
1104 bitmap_intersect_compl_p (bitmap a, bitmap b)
1105 {
1106   bitmap_element *a_elt;
1107   bitmap_element *b_elt;
1108   unsigned ix;
1109   for (a_elt = a->first, b_elt = b->first;
1110        a_elt && b_elt;)
1111     {
1112       if (a_elt->indx < b_elt->indx)
1113         return true;
1114       else if (b_elt->indx < a_elt->indx)
1115         b_elt = b_elt->next;
1116       else
1117         {
1118           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1119             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1120               return true;
1121           a_elt = a_elt->next;
1122           b_elt = b_elt->next;
1123         }
1124     }
1125   return a_elt != NULL;
1126 }
1127
1128 \f
1129 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1130
1131 bool
1132 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1133 {
1134   bitmap_head tmp;
1135   bool changed;
1136
1137   bitmap_initialize (&tmp, &bitmap_default_obstack);
1138   bitmap_and_compl (&tmp, from1, from2);
1139   changed = bitmap_ior (dst, a, &tmp);
1140   bitmap_clear (&tmp);
1141
1142   return changed;
1143 }
1144
1145 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1146
1147 bool
1148 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1149 {
1150   bitmap_head tmp;
1151   bool changed;
1152
1153   bitmap_initialize (&tmp, &bitmap_default_obstack);
1154   bitmap_and_compl (&tmp, from1, from2);
1155   changed = bitmap_ior_into (a, &tmp);
1156   bitmap_clear (&tmp);
1157
1158   return changed;
1159 }
1160 \f
1161 /* Debugging function to print out the contents of a bitmap.  */
1162
1163 void
1164 debug_bitmap_file (FILE *file, bitmap head)
1165 {
1166   bitmap_element *ptr;
1167
1168   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
1169            " current = " HOST_PTR_PRINTF " indx = %u\n",
1170            (void *) head->first, (void *) head->current, head->indx);
1171
1172   for (ptr = head->first; ptr; ptr = ptr->next)
1173     {
1174       unsigned int i, j, col = 26;
1175
1176       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
1177                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
1178                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1179
1180       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1181         for (j = 0; j < BITMAP_WORD_BITS; j++)
1182           if ((ptr->bits[i] >> j) & 1)
1183             {
1184               if (col > 70)
1185                 {
1186                   fprintf (file, "\n\t\t\t");
1187                   col = 24;
1188                 }
1189
1190               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1191                                      + i * BITMAP_WORD_BITS + j));
1192               col += 4;
1193             }
1194
1195       fprintf (file, " }\n");
1196     }
1197 }
1198
1199 /* Function to be called from the debugger to print the contents
1200    of a bitmap.  */
1201
1202 void
1203 debug_bitmap (bitmap head)
1204 {
1205   debug_bitmap_file (stdout, head);
1206 }
1207
1208 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1209    it does not print anything but the bits.  */
1210
1211 void
1212 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1213 {
1214   const char *comma = "";
1215   unsigned i;
1216   bitmap_iterator bi;
1217
1218   fputs (prefix, file);
1219   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1220     {
1221       fprintf (file, "%s%d", comma, i);
1222       comma = ", ";
1223     }
1224   fputs (suffix, file);
1225 }
1226
1227 #include "gt-bitmap.h"