gcc/bitmap.c

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