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 #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. Returns true if A changes */
 704
 705 bool
 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   BITMAP_WORD changed = 0;
 712
 713   gcc_assert (a != b);
 714   while (a_elt && b_elt)
 715     {
 716       if (a_elt->indx < b_elt->indx)
 717         a_elt = a_elt->next;
 718       else if (b_elt->indx < a_elt->indx)
 719         b_elt = b_elt->next;
 720       else
 721         {
 722           /* Matching elts, generate A &= ~B.  */
 723           unsigned ix;
 724           BITMAP_WORD ior = 0;
 725
 726           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 727             {
 728               BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix];
 729               BITMAP_WORD r = a_elt->bits[ix] ^ cleared;
 730
 731               a_elt->bits[ix] = r;
 732               changed |= cleared;
 733               ior |= r;
 734             }
 735           next = a_elt->next;
 736           if (!ior)
 737             bitmap_element_free (a, a_elt);
 738           a_elt = next;
 739           b_elt = b_elt->next;
 740         }
 741     }
 742   gcc_assert (!a->current == !a->first);
 743   gcc_assert (!a->current || a->indx == a->current->indx);
 744   return changed != 0;
 745 }
 746
 747 /* DST = A | B.  Return true if DST changes.  */
 748
 749 bool
 750 bitmap_ior (bitmap dst, bitmap a, bitmap b)
 751 {
 752   bitmap_element *dst_elt = dst->first;
 753   bitmap_element *a_elt = a->first;
 754   bitmap_element *b_elt = b->first;
 755   bitmap_element *dst_prev = NULL;
 756   bool changed = false;
 757
 758   gcc_assert (dst != a && dst != b && a != b);
 759   while (a_elt || b_elt)
 760     {
 761       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 762         {
 763           /* Matching elts, generate A | B.  */
 764           unsigned ix;
 765
 766           if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
 767             {
 768               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 769                 {
 770                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 771
 772                   if (r != dst_elt->bits[ix])
 773                     {
 774                       dst_elt->bits[ix] = r;
 775                       changed = true;
 776                     }
 777                 }
 778             }
 779           else
 780             {
 781               changed = true;
 782               if (!dst_elt)
 783                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 784               dst_elt->indx = a_elt->indx;
 785               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 786                 {
 787                   BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 788
 789                   dst_elt->bits[ix] = r;
 790                 }
 791             }
 792           a_elt = a_elt->next;
 793           b_elt = b_elt->next;
 794           dst_prev = dst_elt;
 795           dst_elt = dst_elt->next;
 796         }
 797       else
 798         {
 799           /* Copy a single element.  */
 800           bitmap_element *src;
 801
 802           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 803             {
 804               src = a_elt;
 805               a_elt = a_elt->next;
 806             }
 807           else
 808             {
 809               src = b_elt;
 810               b_elt = b_elt->next;
 811             }
 812
 813           if (!changed && dst_elt && dst_elt->indx == src->indx)
 814             {
 815               unsigned ix;
 816
 817               for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 818                 if (src->bits[ix] != dst_elt->bits[ix])
 819                   {
 820                     dst_elt->bits[ix] = src->bits[ix];
 821                     changed = true;
 822                   }
 823             }
 824           else
 825             {
 826               changed = true;
 827               if (!dst_elt)
 828                 dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 829               dst_elt->indx = src->indx;
 830               memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 831             }
 832
 833           dst_prev = dst_elt;
 834           dst_elt = dst_elt->next;
 835         }
 836     }
 837
 838   if (dst_elt)
 839     {
 840       changed = true;
 841       bitmap_elt_clear_from (dst, dst_elt);
 842     }
 843   gcc_assert (!dst->current == !dst->first);
 844   if (dst->current)
 845     dst->indx = dst->current->indx;
 846   return changed;
 847 }
 848
 849 /* A |= B.  Return true if A changes.  */
 850
 851 bool
 852 bitmap_ior_into (bitmap a, bitmap b)
 853 {
 854   bitmap_element *a_elt = a->first;
 855   bitmap_element *b_elt = b->first;
 856   bitmap_element *a_prev = NULL;
 857   bool changed = false;
 858
 859   gcc_assert (a != b);
 860   while (b_elt)
 861     {
 862       if (!a_elt || b_elt->indx < a_elt->indx)
 863         {
 864           /* Copy b_elt.  */
 865           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 866
 867           dst->indx = b_elt->indx;
 868           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
 869           a_prev = dst;
 870           b_elt = b_elt->next;
 871           changed = true;
 872         }
 873       else if (a_elt->indx < b_elt->indx)
 874         {
 875           a_prev = a_elt;
 876           a_elt = a_elt->next;
 877         }
 878       else
 879         {
 880           /* Matching elts, generate A |= B.  */
 881           unsigned ix;
 882
 883           if (changed)
 884             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 885               {
 886                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 887
 888                 a_elt->bits[ix] = r;
 889               }
 890           else
 891             for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 892               {
 893                 BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
 894
 895                 if (a_elt->bits[ix] != r)
 896                   {
 897                     changed = true;
 898                     a_elt->bits[ix] = r;
 899                   }
 900               }
 901           b_elt = b_elt->next;
 902           a_prev = a_elt;
 903           a_elt = a_elt->next;
 904         }
 905     }
 906   gcc_assert (!a->current == !a->first);
 907   if (a->current)
 908     a->indx = a->current->indx;
 909   return changed;
 910 }
 911
 912 /* DST = A ^ B  */
 913
 914 void
 915 bitmap_xor (bitmap dst, bitmap a, bitmap b)
 916 {
 917   bitmap_element *dst_elt = dst->first;
 918   bitmap_element *a_elt = a->first;
 919   bitmap_element *b_elt = b->first;
 920   bitmap_element *dst_prev = NULL;
 921
 922   gcc_assert (dst != a && dst != b && a != b);
 923   while (a_elt || b_elt)
 924     {
 925       if (a_elt && b_elt && a_elt->indx == b_elt->indx)
 926         {
 927           /* Matching elts, generate A ^ B.  */
 928           unsigned ix;
 929           BITMAP_WORD ior = 0;
 930
 931           if (!dst_elt)
 932             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 933
 934           dst_elt->indx = a_elt->indx;
 935           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
 936             {
 937               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
 938
 939               ior |= r;
 940               dst_elt->bits[ix] = r;
 941             }
 942           a_elt = a_elt->next;
 943           b_elt = b_elt->next;
 944           if (ior)
 945             {
 946               dst_prev = dst_elt;
 947               dst_elt = dst_elt->next;
 948             }
 949         }
 950       else
 951         {
 952           /* Copy a single element.  */
 953           bitmap_element *src;
 954
 955           if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
 956             {
 957               src = a_elt;
 958               a_elt = a_elt->next;
 959             }
 960           else
 961             {
 962               src = b_elt;
 963               b_elt = b_elt->next;
 964             }
 965
 966           if (!dst_elt)
 967             dst_elt = bitmap_elt_insert_after (dst, dst_prev);
 968
 969           dst_elt->indx = src->indx;
 970           memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
 971           dst_prev = dst_elt;
 972           dst_elt = dst_elt->next;
 973         }
 974     }
 975   bitmap_elt_clear_from (dst, dst_elt);
 976   gcc_assert (!dst->current == !dst->first);
 977   if (dst->current)
 978     dst->indx = dst->current->indx;
 979 }
 980
 981 /* A ^= B */
 982
 983 void
 984 bitmap_xor_into (bitmap a, bitmap b)
 985 {
 986   bitmap_element *a_elt = a->first;
 987   bitmap_element *b_elt = b->first;
 988   bitmap_element *a_prev = NULL;
 989
 990   gcc_assert (a != b);
 991   while (b_elt)
 992     {
 993       if (!a_elt || b_elt->indx < a_elt->indx)
 994         {
 995           /* Copy b_elt.  */
 996           bitmap_element *dst = bitmap_elt_insert_after (a, a_prev);
 997
 998           dst->indx = b_elt->indx;
 999           memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
1000           a_prev = dst;
1001           b_elt = b_elt->next;
1002         }
1003       else if (a_elt->indx < b_elt->indx)
1004         {
1005           a_prev = a_elt;
1006           a_elt = a_elt->next;
1007         }
1008       else
1009         {
1010           /* Matching elts, generate A ^= B.  */
1011           unsigned ix;
1012           BITMAP_WORD ior = 0;
1013           bitmap_element *next = a_elt->next;
1014
1015           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1016             {
1017               BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix];
1018
1019               ior |= r;
1020               a_elt->bits[ix] = r;
1021             }
1022           b_elt = b_elt->next;
1023           if (ior)
1024             a_prev = a_elt;
1025           else
1026             bitmap_element_free (a, a_elt);
1027           a_elt = next;
1028         }
1029     }
1030   gcc_assert (!a->current == !a->first);
1031   if (a->current)
1032     a->indx = a->current->indx;
1033 }
1034
1035 /* Return true if two bitmaps are identical.
1036    We do not bother with a check for pointer equality, as that never
1037    occurs in practice.  */
1038
1039 bool
1040 bitmap_equal_p (bitmap a, bitmap b)
1041 {
1042   bitmap_element *a_elt;
1043   bitmap_element *b_elt;
1044   unsigned ix;
1045
1046   for (a_elt = a->first, b_elt = b->first;
1047        a_elt && b_elt;
1048        a_elt = a_elt->next, b_elt = b_elt->next)
1049     {
1050       if (a_elt->indx != b_elt->indx)
1051         return false;
1052       for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1053         if (a_elt->bits[ix] != b_elt->bits[ix])
1054           return false;
1055     }
1056   return !a_elt && !b_elt;
1057 }
1058
1059 /* Return true if A AND B is not empty.  */
1060
1061 bool
1062 bitmap_intersect_p (bitmap a, bitmap b)
1063 {
1064   bitmap_element *a_elt;
1065   bitmap_element *b_elt;
1066   unsigned ix;
1067
1068   for (a_elt = a->first, b_elt = b->first;
1069        a_elt && b_elt;)
1070     {
1071       if (a_elt->indx < b_elt->indx)
1072         a_elt = a_elt->next;
1073       else if (b_elt->indx < a_elt->indx)
1074         b_elt = b_elt->next;
1075       else
1076         {
1077           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1078             if (a_elt->bits[ix] & b_elt->bits[ix])
1079               return true;
1080           a_elt = a_elt->next;
1081           b_elt = b_elt->next;
1082         }
1083     }
1084   return false;
1085 }
1086
1087 /* Return true if A AND NOT B is not empty.  */
1088
1089 bool
1090 bitmap_intersect_compl_p (bitmap a, bitmap b)
1091 {
1092   bitmap_element *a_elt;
1093   bitmap_element *b_elt;
1094   unsigned ix;
1095   for (a_elt = a->first, b_elt = b->first;
1096        a_elt && b_elt;)
1097     {
1098       if (a_elt->indx < b_elt->indx)
1099         return true;
1100       else if (b_elt->indx < a_elt->indx)
1101         b_elt = b_elt->next;
1102       else
1103         {
1104           for (ix = BITMAP_ELEMENT_WORDS; ix--;)
1105             if (a_elt->bits[ix] & ~b_elt->bits[ix])
1106               return true;
1107           a_elt = a_elt->next;
1108           b_elt = b_elt->next;
1109         }
1110     }
1111   return a_elt != NULL;
1112 }
1113
1114 \f
1115 /* DST = A | (FROM1 & ~FROM2).  Return true if DST changes.  */
1116
1117 bool
1118 bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
1119 {
1120   bitmap_head tmp;
1121   bool changed;
1122
1123   bitmap_initialize (&tmp, &bitmap_default_obstack);
1124   bitmap_and_compl (&tmp, from1, from2);
1125   changed = bitmap_ior (dst, a, &tmp);
1126   bitmap_clear (&tmp);
1127
1128   return changed;
1129 }
1130
1131 /* A |= (FROM1 & ~FROM2).  Return true if A changes.  */
1132
1133 bool
1134 bitmap_ior_and_compl_into (bitmap a, bitmap from1, bitmap from2)
1135 {
1136   bitmap_head tmp;
1137   bool changed;
1138
1139   bitmap_initialize (&tmp, &bitmap_default_obstack);
1140   bitmap_and_compl (&tmp, from1, from2);
1141   changed = bitmap_ior_into (a, &tmp);
1142   bitmap_clear (&tmp);
1143
1144   return changed;
1145 }
1146 \f
1147 /* Debugging function to print out the contents of a bitmap.  */
1148
1149 void
1150 debug_bitmap_file (FILE *file, bitmap head)
1151 {
1152   bitmap_element *ptr;
1153
1154   fprintf (file, "\nfirst = " HOST_PTR_PRINTF
1155            " current = " HOST_PTR_PRINTF " indx = %u\n",
1156            (void *) head->first, (void *) head->current, head->indx);
1157
1158   for (ptr = head->first; ptr; ptr = ptr->next)
1159     {
1160       unsigned int i, j, col = 26;
1161
1162       fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF
1163                " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {",
1164                (void*) ptr, (void*) ptr->next, (void*) ptr->prev, ptr->indx);
1165
1166       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
1167         for (j = 0; j < BITMAP_WORD_BITS; j++)
1168           if ((ptr->bits[i] >> j) & 1)
1169             {
1170               if (col > 70)
1171                 {
1172                   fprintf (file, "\n\t\t\t");
1173                   col = 24;
1174                 }
1175
1176               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
1177                                      + i * BITMAP_WORD_BITS + j));
1178               col += 4;
1179             }
1180
1181       fprintf (file, " }\n");
1182     }
1183 }
1184
1185 /* Function to be called from the debugger to print the contents
1186    of a bitmap.  */
1187
1188 void
1189 debug_bitmap (bitmap head)
1190 {
1191   debug_bitmap_file (stdout, head);
1192 }
1193
1194 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
1195    it does not print anything but the bits.  */
1196
1197 void
1198 bitmap_print (FILE *file, bitmap head, const char *prefix, const char *suffix)
1199 {
1200   const char *comma = "";
1201   unsigned i;
1202   bitmap_iterator bi;
1203
1204   fputs (prefix, file);
1205   EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi)
1206     {
1207       fprintf (file, "%s%d", comma, i);
1208       comma = ", ";
1209     }
1210   fputs (suffix, file);
1211 }
1212
1213 #include "gt-bitmap.h"