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 /* 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 #if BITMAP_ELEMENT_WORDS != 2
 350   unsigned i;
 351 #endif
 352
 353   bitmap_clear (to);
 354
 355   /* Copy elements in forward direction one at a time.  */
 356   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 357     {
 358       bitmap_element *to_elt = bitmap_element_allocate (to);
 359
 360       to_elt->indx = from_ptr->indx;
 361
 362 #if BITMAP_ELEMENT_WORDS == 2
 363       to_elt->bits[0] = from_ptr->bits[0];
 364       to_elt->bits[1] = from_ptr->bits[1];
 365 #else
 366       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 367         to_elt->bits[i] = from_ptr->bits[i];
 368 #endif
 369
 370       /* Here we have a special case of bitmap_element_link, for the case
 371          where we know the links are being entered in sequence.  */
 372       if (to_ptr == 0)
 373         {
 374           to->first = to->current = to_elt;
 375           to->indx = from_ptr->indx;
 376           to_elt->next = to_elt->prev = 0;
 377         }
 378       else
 379         {
 380           to_elt->prev = to_ptr;
 381           to_elt->next = 0;
 382           to_ptr->next = to_elt;
 383         }
 384
 385       to_ptr = to_elt;
 386     }
 387 }
 388 \f
 389 /* Find a bitmap element that would hold a bitmap's bit.
 390    Update the `current' field even if we can't find an element that
 391    would hold the bitmap's bit to make eventual allocation
 392    faster.  */
 393
 394 static inline bitmap_element *
 395 bitmap_find_bit (bitmap head, unsigned int bit)
 396 {
 397   bitmap_element *element;
 398   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 399
 400   if (head->current == 0
 401       || head->indx == indx)
 402     return head->current;
 403
 404   if (head->indx < indx)
 405     /* INDX is beyond head->indx.  Search from head->current
 406        forward.  */
 407     for (element = head->current;
 408          element->next != 0 && element->indx < indx;
 409          element = element->next)
 410       ;
 411
 412   else if (head->indx / 2 < indx)
 413     /* INDX is less than head->indx and closer to head->indx than to
 414        0.  Search from head->current backward.  */
 415     for (element = head->current;
 416          element->prev != 0 && element->indx > indx;
 417          element = element->prev)
 418       ;
 419
 420   else
 421     /* INDX is less than head->indx and closer to 0 than to
 422        head->indx.  Search from head->first forward.  */
 423     for (element = head->first;
 424          element->next != 0 && element->indx < indx;
 425          element = element->next)
 426       ;
 427
 428   /* `element' is the nearest to the one we want.  If it's not the one we
 429      want, the one we want doesn't exist.  */
 430   head->current = element;
 431   head->indx = element->indx;
 432   if (element != 0 && element->indx != indx)
 433     element = 0;
 434
 435   return element;
 436 }
 437 \f
 438 /* Clear a single bit in a bitmap.  */
 439
 440 void
 441 bitmap_clear_bit (bitmap head, int bit)
 442 {
 443   bitmap_element *ptr = bitmap_find_bit (head, bit);
 444
 445   if (ptr != 0)
 446     {
 447       unsigned bit_num  = bit % BITMAP_WORD_BITS;
 448       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 449       ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
 450
 451       /* If we cleared the entire word, free up the element.  */
 452       if (bitmap_element_zerop (ptr))
 453         bitmap_element_free (head, ptr);
 454     }
 455 }
 456
 457 /* Set a single bit in a bitmap.  */
 458
 459 void
 460 bitmap_set_bit (bitmap head, int bit)
 461 {
 462   bitmap_element *ptr = bitmap_find_bit (head, bit);
 463   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 464   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 465   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 466
 467   if (ptr == 0)
 468     {
 469       ptr = bitmap_element_allocate (head);
 470       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 471       ptr->bits[word_num] = bit_val;
 472       bitmap_element_link (head, ptr);
 473     }
 474   else
 475     ptr->bits[word_num] |= bit_val;
 476 }
 477
 478 /* Return whether a bit is set within a bitmap.  */
 479
 480 int
 481 bitmap_bit_p (bitmap head, int bit)
 482 {
 483   bitmap_element *ptr;
 484   unsigned bit_num;
 485   unsigned word_num;
 486
 487   ptr = bitmap_find_bit (head, bit);
 488   if (ptr == 0)
 489     return 0;
 490
 491   bit_num = bit % BITMAP_WORD_BITS;
 492   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 493
 494   return (ptr->bits[word_num] >> bit_num) & 1;
 495 }
 496 \f
 497 /* Return the bit number of the first set bit in the bitmap.  The
 498    bitmap must be non-empty.  */
 499
 500 unsigned
 501 bitmap_first_set_bit (bitmap a)
 502 {
 503   bitmap_element *elt = a->first;
 504   unsigned bit_no;
 505   BITMAP_WORD word;
 506   unsigned ix;
 507
 508   gcc_assert (elt);
 509   bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
 510   for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
 511     {
 512       word = elt->bits[ix];
 513       if (word)
 514         goto found_bit;
 515     }
 516   gcc_unreachable ();
 517  found_bit:
 518   bit_no += ix * BITMAP_WORD_BITS;
 519
 520 #if GCC_VERSION >= 3004
 521   gcc_assert (sizeof(long) == sizeof (word));
 522   bit_no += __builtin_ctzl (word);
 523 #else
 524   /* Binary search for the first set bit.  */
 525 #if BITMAP_WORD_BITS > 64
 526 #error "Fill out the table."
 527 #endif
 528 #if BITMAP_WORD_BITS > 32
 529   if (!(word & 0xffffffff))
 530     word >>= 32, bit_no += 32;
 531 #endif
 532   if (!(word & 0xffff))
 533     word >>= 16, bit_no += 16;
 534   if (!(word & 0xff))
 535     word >>= 8, bit_no += 8;
 536   if (!(word & 0xf))
 537     word >>= 4, bit_no += 4;
 538   if (!(word & 0x3))
 539     word >>= 2, bit_no += 2;
 540   if (!(word & 0x1))
 541     word >>= 1, bit_no += 1;
 542
 543  gcc_assert (word & 1);
 544 #endif
 545  return bit_no;
 546 }
 547 \f
 548
 549 /* DST = A & B.  */
 550
 551 void
 552 bitmap_and (bitmap dst, bitmap a, bitmap b)
 553 {
 554   bitmap_element *dst_elt = dst->first;
 555   bitmap_element *a_elt = a->first;
 556   bitmap_element *b_elt = b->first;
 557   bitmap_element *dst_prev = NULL;
 558
 559   gcc_assert (dst != a && dst != b && a != b);
 560   while (a_elt && b_elt)
 561     {
 562       if (a_elt->indx < b_elt->indx)
 563         a_elt = a_elt->next;
 564       else if (b_elt->indx < a_elt->indx)
 565         b_elt = b_elt->next;
 566       else
 567         {
 568           /* Matching elts, generate A & B.  */
 569           unsigned ix;
 570           BITMAP_WORD ior = 0;
 571
 572           if (!dst_elt)
 573             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 574
 575           dst_elt->indx = a_elt->indx;
 576           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 577             {
 578               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 579
 580               dst_elt->bits[ix] = r;
 581               ior |= r;
 582             }
 583           if (ior)
 584             {
 585               dst_prev = dst_elt;
 586               dst_elt = dst_elt->next;
 587             }
 588           a_elt = a_elt->next;
 589           b_elt = b_elt->next;
 590         }
 591     }
 592   bitmap_elt_clear_from (dst, dst_elt);
 593   gcc_assert (!dst->current == !dst->first);
 594   if (dst->current)
 595     dst->indx = dst->current->indx;
 596 }
 597
 598 /* A &= B.  */
 599
 600 void
 601 bitmap_and_into (bitmap a, bitmap b)
 602 {
 603   bitmap_element *a_elt = a->first;
 604   bitmap_element *b_elt = b->first;
 605   bitmap_element *next;
 606
 607   gcc_assert (a != b);
 608   while (a_elt && b_elt)
 609     {
 610       if (a_elt->indx < b_elt->indx)
 611         {
 612           next = a_elt->next;
 613           bitmap_element_free (a, a_elt);
 614           a_elt = next;
 615         }
 616       else if (b_elt->indx < a_elt->indx)
 617         b_elt = b_elt->next;
 618       else
 619         {
 620           /* Matching elts, generate A &= B.  */
 621           unsigned ix;
 622           BITMAP_WORD ior = 0;
 623
 624           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 625             {
 626               BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix];
 627
 628               a_elt->bits[ix] = r;
 629               ior |= r;
 630             }
 631           next = a_elt->next;
 632           if (!ior)
 633             bitmap_element_free (a, a_elt);
 634           a_elt = next;
 635           b_elt = b_elt->next;
 636         }
 637     }
 638   bitmap_elt_clear_from (a, a_elt);
 639   gcc_assert (!a->current == !a->first);
 640   gcc_assert (!a->current || a->indx == a->current->indx);
 641 }
 642
 643 /* DST = A & ~B  */
 644
 645 void
 646 bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
 647 {
 648   bitmap_element *dst_elt = dst->first;
 649   bitmap_element *a_elt = a->first;
 650   bitmap_element *b_elt = b->first;
 651   bitmap_element *dst_prev = NULL;
 652
 653   gcc_assert (dst != a && dst != b && a != b);
 654
 655   while (a_elt)
 656     {
 657       if (!b_elt || a_elt->indx < b_elt->indx)
 658         {
 659           /* Copy a_elt.  */
 660           if (!dst_elt)
 661             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 662
 663           dst_elt->indx = a_elt->indx;
 664           memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
 665           dst_prev = dst_elt;
 666           dst_elt = dst_elt->next;
 667           a_elt = a_elt->next;
 668         }
 669       else if (b_elt->indx < a_elt->indx)
 670         b_elt = b_elt->next;
 671       else
 672         {
 673           /* Matching elts, generate A & ~B.  */
 674           unsigned ix;
 675           BITMAP_WORD ior = 0;
 676
 677           if (!dst_elt)
 678             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 679
 680           dst_elt->indx = a_elt->indx;
 681           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 682             {
 683               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 684
 685               dst_elt->bits[ix] = r;
 686               ior |= r;
 687             }
 688           if (ior)
 689             {
 690               dst_prev = dst_elt;
 691               dst_elt = dst_elt->next;
 692             }
 693           a_elt = a_elt->next;
 694           b_elt = b_elt->next;
 695         }
 696     }
 697   bitmap_elt_clear_from (dst, dst_elt);
 698   gcc_assert (!dst->current == !dst->first);
 699   if (dst->current)
 700     dst->indx = dst->current->indx;
 701 }
 702
 703 /* A &= ~B */
 704
 705 void
 706 bitmap_and_compl_into (bitmap a, bitmap b)
 707 {
 708   bitmap_element *a_elt = a->first;
 709   bitmap_element *b_elt = b->first;
 710   bitmap_element *next;
 711
 712   gcc_assert (a != b);
 713   while (a_elt && b_elt)
 714     {
 715       if (a_elt->indx < b_elt->indx)
 716         a_elt = a_elt->next;
 717       else if (b_elt->indx < a_elt->indx)
 718         b_elt = b_elt->next;
 719       else
 720         {
 721           /* Matching elts, generate A &= ~B.  */
 722           unsigned ix;
 723           BITMAP_WORD ior = 0;
 724
 725           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 726             {
 727               BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
 728
 729               a_elt->bits[ix] = r;
 730               ior |= r;
 731             }
 732           next = a_elt->next;
 733           if (!ior)
 734             bitmap_element_free (a, a_elt);
 735           a_elt = next;
 736           b_elt = b_elt->next;
 737         }
 738     }
 739   gcc_assert (!a->current == !a->first);
 740   gcc_assert (!a->current || a->indx == a->current->indx);
 741 }
 742
 743 /* DST = A | B.  Return true if DST changes.  */
 744
 745 bool
 746 bitmap_ior (bitmap dst, bitmap a, bitmap b)
 747 {
 748   bitmap_element *dst_elt = dst->first;
 749   bitmap_element *a_elt = a->first;
 750   bitmap_element *b_elt = b->first;
 751   bitmap_element *dst_prev = NULL;
 752   bool changed = false;
 753
 754   gcc_assert (dst != a && dst != b && a != b);
 755   while (a_elt || b_elt)
 756     {
 757       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 758         {
 759           /* Matching elts, generate A | B.  */
 760           unsigned ix;
 761
 762           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
 763             {
 764               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 765                 {
 766                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 767
 768                   if (r != dst_elt->bits[ix])
 769                     {
 770                       dst_elt->bits[ix] = r;
 771                       changed = true;
 772                     }
 773                 }
 774             }
 775           else
 776             {
 777               changed = true;
 778               if (!dst_elt)
 779                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 780               dst_elt->indx = a_elt->indx;
 781               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 782                 {
 783                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 784
 785                   dst_elt->bits[ix] = r;
 786                 }
 787             }
 788           a_elt = a_elt->next;
 789           b_elt = b_elt->next;
 790           dst_prev = dst_elt;
 791           dst_elt = dst_elt->next;
 792         }
 793       else
 794         {
 795           /* Copy a single element.  */
 796           bitmap_element *src;
 797
 798           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 799             {
 800               src = a_elt;
 801               a_elt = a_elt->next;
 802             }
 803           else
 804             {
 805               src = b_elt;
 806               b_elt = b_elt->next;
 807             }
 808
 809           if (!changed && dst_elt && dst_elt->indx == src->indx)
 810             {
 811               unsigned ix;
 812
 813               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 814                 if (src->bits[ix] != dst_elt->bits[ix])
 815                   {
 816                     dst_elt->bits[ix] = src->bits[ix];
 817                     changed = true;
 818                   }
 819             }
 820           else
 821             {
 822               changed = true;
 823               if (!dst_elt)
 824                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 825               dst_elt->indx = src->indx;
 826               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 827             }
 828
 829           dst_prev = dst_elt;
 830           dst_elt = dst_elt->next;
 831         }
 832     }
 833
 834   if (dst_elt)
 835     {
 836       changed = true;
 837       bitmap_elt_clear_from (dst, dst_elt);
 838     }
 839   gcc_assert (!dst->current == !dst->first);
 840   if (dst->current)
 841     dst->indx = dst->current->indx;
 842   return changed;
 843 }
 844
 845 /* A |= B.  Return true if A changes.  */
 846
 847 bool
 848 bitmap_ior_into (bitmap a, bitmap b)
 849 {
 850   bitmap_element *a_elt = a->first;
 851   bitmap_element *b_elt = b->first;
 852   bitmap_element *a_prev = NULL;
 853   bool changed = false;
 854
 855   gcc_assert (a != b);
 856   while (b_elt)
 857     {
 858       if (!a_elt || b_elt->indx < a_elt->indx)
 859         {
 860           /* Copy b_elt.  */
 861           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 862
 863           dst->indx = b_elt->indx;
 864           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 865           a_prev = dst;
 866           b_elt = b_elt->next;
 867           changed = true;
 868         }
 869       else if (a_elt->indx < b_elt->indx)
 870         {
 871           a_prev = a_elt;
 872           a_elt = a_elt->next;
 873         }
 874       else
 875         {
 876           /* Matching elts, generate A |= B.  */
 877           unsigned ix;
 878
 879           if (changed)
 880             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 881               {
 882                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 883
 884                 a_elt->bits[ix] = r;
 885               }
 886           else
 887             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 888               {
 889                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 890
 891                 if (a_elt->bits[ix] != r)
 892                   {
 893                     changed = true;
 894                     a_elt->bits[ix] = r;
 895                   }
 896               }
 897           b_elt = b_elt->next;
 898           a_prev = a_elt;
 899           a_elt = a_elt->next;
 900         }
 901     }
 902   gcc_assert (!a->current == !a->first);
 903   if (a->current)
 904     a->indx = a->current->indx;
 905   return changed;
 906 }
 907
 908 /* DST = A ^ B  */
 909
 910 void
 911 bitmap_xor (bitmap dst, bitmap a, bitmap b)
 912 {
 913   bitmap_element *dst_elt = dst->first;
 914   bitmap_element *a_elt = a->first;
 915   bitmap_element *b_elt = b->first;
 916   bitmap_element *dst_prev = NULL;
 917
 918   gcc_assert (dst != a && dst != b && a != b);
 919   while (a_elt || b_elt)
 920     {
 921       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 922         {
 923           /* Matching elts, generate A ^ B.  */
 924           unsigned ix;
 925           BITMAP_WORD ior = 0;
 926
 927           if (!dst_elt)
 928             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 929
 930           dst_elt->indx = a_elt->indx;
 931           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 932             {
 933               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
 934
 935               ior |= r;
 936               dst_elt->bits[ix] = r;
 937             }
 938           a_elt = a_elt->next;
 939           b_elt = b_elt->next;
 940           if (ior)
 941             {
 942               dst_prev = dst_elt;
 943               dst_elt = dst_elt->next;
 944             }
 945         }
 946       else
 947         {
 948           /* Copy a single element.  */
 949           bitmap_element *src;
 950
 951           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 952             {
 953               src = a_elt;
 954               a_elt = a_elt->next;
 955             }
 956           else
 957             {
 958               src = b_elt;
 959               b_elt = b_elt->next;
 960             }
 961
 962           if (!dst_elt)
 963             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 964
 965           dst_elt->indx = src->indx;
 966           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 967           dst_prev = dst_elt;
 968           dst_elt = dst_elt->next;
 969         }
 970     }
 971   bitmap_elt_clear_from (dst, dst_elt);
 972   gcc_assert (!dst->current == !dst->first);
 973   if (dst->current)
 974     dst->indx = dst->current->indx;
 975 }
 976
 977 /* A ^= B */
 978
 979 void
 980 bitmap_xor_into (bitmap a, bitmap b)
 981 {
 982   bitmap_element *a_elt = a->first;
 983   bitmap_element *b_elt = b->first;
 984   bitmap_element *a_prev = NULL;
 985
 986   gcc_assert (a != b);
 987   while (b_elt)
 988     {
 989       if (!a_elt || b_elt->indx < a_elt->indx)
 990         {
 991           /* Copy b_elt.  */
 992           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 993
 994           dst->indx = b_elt->indx;
 995           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 996           a_prev = dst;
 997           b_elt = b_elt->next;
 998         }
 999       else if (a_elt->indx < b_elt->indx)
1000         {
1001           a_prev = a_elt;
1002           a_elt = a_elt->next;
1003         }
1004       else
1005         {
1006           /* Matching elts, generate A ^= B.  */
1007           unsigned ix;
1008           BITMAP_WORD ior = 0;
1009           bitmap_element *next = a_elt->next;
1010
1011           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1012             {
1013               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1014
1015               ior |= r;
1016               a_elt->bits[ix] = r;
1017             }
1018           b_elt = b_elt->next;
1019           if (ior)
1020             a_prev = a_elt;
1021           else
1022             bitmap_element_free (a, a_elt);
1023           a_elt = next;
1024         }
1025     }
1026   gcc_assert (!a->current == !a->first);
1027   if (a->current)
1028     a->indx = a->current->indx;
1029 }
1030
1031 /* Return true if two bitmaps are identical.
1032    We do not bother with a check for pointer equality, as that never
1033    occurs in practice.  */
1034
1035 bool
1036 bitmap_equal_p (bitmap a, bitmap b)
1037 {
1038   bitmap_element *a_elt;
1039   bitmap_element *b_elt;
1040   unsigned ix;
1041
1042   for (a_elt = a->first, b_elt = b->first;
1043        a_elt && b_elt;
1044        a_elt = a_elt->next, b_elt = b_elt->next)
1045     {
1046       if (a_elt->indx != b_elt->indx)
1047         return false;
1048       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1049         if (a_elt->bits[ix] != b_elt->bits[ix])
1050           return false;
1051     }
1052   return !a_elt && !b_elt;
1053 }
1054
1055 /* Return true if A AND B is not empty.  */
1056
1057 bool
1058 bitmap_intersect_p (bitmap a, bitmap b)
1059 {
1060   bitmap_element *a_elt;
1061   bitmap_element *b_elt;
1062   unsigned ix;
1063
1064   for (a_elt = a->first, b_elt = b->first;
1065        a_elt && b_elt;)
1066     {
1067       if (a_elt->indx < b_elt->indx)
1068         a_elt = a_elt->next;
1069       else if (b_elt->indx < a_elt->indx)
1070         b_elt = b_elt->next;
1071       else
1072         {
1073           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1074             if (a_elt->bits[ix] & b_elt->bits[ix])
1075               return true;
1076           a_elt = a_elt->next;
1077           b_elt = b_elt->next;
1078         }
1079     }
1080   return false;
1081 }
1082
1083 /* Return true if A AND NOT B is not empty.  */
1084
1085 bool
1086 bitmap_intersect_compl_p (bitmap a, bitmap b)
1087 {
1088   bitmap_element *a_elt;
1089   bitmap_element *b_elt;
1090   unsigned ix;
1091   for (a_elt = a->first, b_elt = b->first;
1092        a_elt && b_elt;)
1093     {
1094       if (a_elt->indx < b_elt->indx)
1095         return true;
1096       else if (b_elt->indx < a_elt->indx)
1097         b_elt = b_elt->next;
1098       else
1099         {
1100           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1101             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1102               return true;
1103           a_elt = a_elt->next;
1104           b_elt = b_elt->next;
1105         }
1106     }
1107   return a_elt != NULL;
1108 }
1109
1110 \f
1111 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1112
1113 bool
1114 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1115 {
1116   bitmap_head tmp;
1117   bool changed;
1118
1119   bitmap_initialize (&tmp, &bitmap_default_obstack);
1120   bitmap_and_compl (&tmp, from1, from2);
1121   changed = bitmap_ior (dst, a, &tmp);
1122   bitmap_clear (&tmp);
1123
1124   return changed;
1125 }
1126
1127 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1128
1129 bool
1130 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1131 {
1132   bitmap_head tmp;
1133   bool changed;
1134
1135   bitmap_initialize (&tmp, &bitmap_default_obstack);
1136   bitmap_and_compl (&tmp, from1, from2);
1137   changed = bitmap_ior_into (a, &tmp);
1138   bitmap_clear (&tmp);
1139
1140   return changed;
1141 }
1142 \f
1143 /* Debugging function to print out the contents of a bitmap.  */
1144
1145 void
1146 debug_bitmap_file (FILE *file, bitmap head)
1147 {
1148   bitmap_element *ptr;
1149
1150   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
1151            " current = " HOST_PTR_PRINTF " indx = %u\n",
1152            (void *) head->first, (void *) head->current, head->indx);
1153
1154   for (ptr = head->first; ptr; ptr = ptr->next)
1155     {
1156       unsigned int i, j, col = 26;
1157
1158       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
1159                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
1160                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1161
1162       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1163         for (j = 0; j < BITMAP_WORD_BITS; j++)
1164           if ((ptr->bits[i] >> j) & 1)
1165             {
1166               if (col > 70)
1167                 {
1168                   fprintf (file, "\n\t\t\t");
1169                   col = 24;
1170                 }
1171
1172               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1173                                      + i * BITMAP_WORD_BITS + j));
1174               col += 4;
1175             }
1176
1177       fprintf (file, " }\n");
1178     }
1179 }
1180
1181 /* Function to be called from the debugger to print the contents
1182    of a bitmap.  */
1183
1184 void
1185 debug_bitmap (bitmap head)
1186 {
1187   debug_bitmap_file (stdout, head);
1188 }
1189
1190 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1191    it does not print anything but the bits.  */
1192
1193 void
1194 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1195 {
1196   const char *comma = "";
1197   unsigned i;
1198   bitmap_iterator bi;
1199
1200   fputs (prefix, file);
1201   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1202     {
1203       fprintf (file, "%s%d", comma, i);
1204       comma = ", ";
1205     }
1206   fputs (suffix, file);
1207 }
1208
1209 #include "gt-bitmap.h"