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