gcc/ebitmap.c

   1 /* Sparse array-based bitmaps.
   2    Copyright (C) 2007 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dberlin@dberlin.org>
   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 "ebitmap.h"
  30
  31 /* The ebitmap data structure is a sparse bitmap structure that works
  32    by having two pieces:
  33    1. An array of all nonzero words in the structures, organized as
  34    an array of HOST_WIDE_INT's.
  35    2. A non-sparse bitmap saying which bitmap words are present in the
  36    array.
  37
  38    As a consequence of this representation, testing whether a bit
  39    exists in the bitmap is faster than linked-list bitmaps.  For bits
  40    in words that are all zero, the time to test is O(1).  For bits in
  41    words that exist, it requires O(n/sizeof(word)) time to perform the
  42    test (ignoring the one element cache).  It also has much better
  43    locality than linked-list bitmaps.
  44
  45    To test whether a bit exists, we do the following:
  46    1. Test whether the word the bit would appear in exists in the
  47    bitmap (O(1) check of the mask).  If not, fail.
  48
  49    2. Population count the mask up to the word containing the bit, to
  50    find the place in the array the word would be (popcount is cached,
  51    but this is just as slow as the linked-list bitmap)
  52    3. Test the word to see if the bit exists.
  53
  54    Just like linked-list bitmaps, we cache the last element that has
  55    been tested in order to speed up common access patterns.
  56
  57    Most of the other speedups are simply due to better locality of the
  58    single contiguous array.
  59
  60    As would be expected in a structure like this, insertion into an
  61    empty word in the middle requires moving bits to make room for the
  62    new word.   As most operations that perform sets perform them in
  63    order, this is rarely a problem.  We also take advantage of the
  64    same element cache to make repeated sets to the same word O(1).
  65
  66    Operations on the entire bitmap are also more efficient than linked
  67    list bitmaps, as they are all operating on contiguous memory, and
  68    can be easily vectorized.  They are all O(number of words) +
  69    O(number of bits that may end up in the destination), as the
  70    appropriate operation is first performed on the word mask, and then
  71    only those elements that may generate results are touched.
  72
  73    Memory wise, the ebitmap starts out using less memory than the
  74    linked-list bitmap, but its size in memory is technically bounded
  75    by ((index of the highest bit set) / (size of a word) + (index of
  76    the highest bit set) / ((size of a word) * (size of a word))) This
  77    is because the mask is non-sparse.  The mask could be transformed
  78    into a sparse bitmap at the cost of making bit testing
  79    *theoretically* slower (real world numbers have not been computed
  80    yet as to whether it matters or not).  */
  81
  82 /* #define EBITMAP_DEBUGGING  */
  83
  84 /* Find the last set bit in ebitmap MAP.  */
  85
  86 int
  87 ebitmap_last_set_bit (ebitmap map)
  88 {
  89   unsigned int i = 0;
  90   ebitmap_iterator ebi;
  91   bool foundbit = false;
  92
  93   /* This is not the fastest way to do this, we could simply look for
  94      the popcount, and start there, but this function is not used
  95      anywhere speed critical.  */
  96   EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi)
  97     {
  98       foundbit = true;
  99     }
 100
 101
 102   if (foundbit)
 103     return i;
 104   return -1;
 105 }
 106
 107 /* Grow or shrink the internal word array for MAP to NEWSIZE
 108    elements.  */
 109
 110 static inline void
 111 ebitmap_array_grow (ebitmap map, unsigned int newsize)
 112 {
 113   if (newsize <= map->n_elts)
 114     {
 115       map->n_elts = newsize;
 116       return;
 117     }
 118
 119   newsize += newsize / 4;
 120
 121   map->n_elts = newsize;
 122   map->elts = xrealloc (map->elts, sizeof (EBITMAP_ELT_TYPE) * newsize);
 123 }
 124
 125 /* Grow the internal word array for MAP so it is at least SIZE
 126    elements.  Will not shrink the array if it is already big
 127    enough.  */
 128
 129 static inline void
 130 ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
 131 {
 132   if (size >= map->n_elts)
 133     ebitmap_array_grow (map, size + 1);
 134 }
 135
 136 /* Retrieve the IDX'th element from the word array for MAP.  */
 137
 138 static inline EBITMAP_ELT_TYPE
 139 ebitmap_array_get (ebitmap map, unsigned int idx)
 140 {
 141   gcc_assert (idx < map->n_elts);
 142   return map->elts[idx];
 143 }
 144
 145 /* Retrieve a pointer to the IDX'th element from the word array for
 146    MAP.  If the element index is greater than the size of the array,
 147    the array will be grown to the correct size.  */
 148
 149 static inline EBITMAP_ELT_TYPE *
 150 ebitmap_array_grow_get (ebitmap map, unsigned int idx)
 151 {
 152   if (idx >= map->n_elts)
 153     ebitmap_array_grow (map, idx + 1);
 154   return &map->elts[idx];
 155 }
 156
 157 /* Initialize the internal word array for MAP, so that it is SIZE
 158    elements.  */
 159
 160 static inline void
 161 ebitmap_array_init (ebitmap map, unsigned int size)
 162 {
 163   if (size > 0)
 164     {
 165       map->elts = xmalloc (sizeof (EBITMAP_ELT_TYPE) * size);
 166       map->n_elts = size;
 167     }
 168   else
 169     {
 170       map->n_elts = 0;
 171       map->elts = NULL;
 172     }
 173 }
 174
 175 /* Free the internal word array for MAP.  */
 176
 177 static inline void
 178 ebitmap_array_clear (ebitmap map)
 179 {
 180   if (map->elts)
 181     {
 182       free (map->elts);
 183       map->elts = NULL;
 184     }
 185   map->n_elts = 0;
 186 }
 187
 188 /* Clear ebitmap MAP.  */
 189
 190 void
 191 ebitmap_clear (ebitmap map)
 192 {
 193   ebitmap_array_clear (map);
 194   sbitmap_zero (map->wordmask);
 195   map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
 196   map->numwords = 0;
 197   map->cache = NULL;
 198   map->cacheindex = 0;
 199 }
 200
 201 /* Allocate an ebitmap with enough room for SIZE bits to start out.  */
 202
 203 ebitmap
 204 ebitmap_alloc (unsigned int size)
 205 {
 206   ebitmap ret = xmalloc (sizeof (struct ebitmap_def));
 207   if (size == 0)
 208     size = EBITMAP_ELT_BITS;
 209   ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS);
 210   ret->wordmask = sbitmap_alloc_with_popcount (size);
 211   sbitmap_zero (ret->wordmask);
 212   ret->numwords = 0;
 213   ret->cache = NULL;
 214   ret->cacheindex = 0;
 215
 216   return ret;
 217 }
 218
 219 /* Clear BIT from ebitmap MAP.  */
 220
 221 void
 222 ebitmap_clear_bit (ebitmap map, unsigned int bit)
 223 {
 224   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
 225   unsigned int eltwordindex = 0;
 226   unsigned int bitindex, shift;
 227   bool have_eltwordindex = false;
 228   EBITMAP_ELT_TYPE *elt_ptr;
 229
 230   /* If the bit can't exist in our bitmap, just return.  */
 231   if (map->numwords == 0)
 232     return;
 233
 234   if (wordindex >= map->wordmask->n_bits
 235       || !TEST_BIT (map->wordmask, wordindex))
 236     return;
 237
 238   if (map->cache != NULL && map->cacheindex == wordindex)
 239     elt_ptr = map->cache;
 240   else
 241     {
 242       eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
 243       elt_ptr = &map->elts[eltwordindex];
 244       have_eltwordindex = true;
 245     }
 246
 247   bitindex = bit % EBITMAP_ELT_BITS;
 248   shift = bitindex;
 249
 250   *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift);
 251
 252   /* Clear out the empty words.  */
 253   if (*(elt_ptr) == 0)
 254     {
 255       if (!have_eltwordindex)
 256         eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
 257
 258       if (map->cache != NULL && map->cacheindex == eltwordindex)
 259         map->cache = NULL;
 260
 261       RESET_BIT (map->wordmask, wordindex);
 262
 263       memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
 264               sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
 265       map->numwords--;
 266     }
 267 }
 268
 269 /* Set BIT in ebitmap MAP.  */
 270
 271 void
 272 ebitmap_set_bit (ebitmap map, unsigned int bit)
 273 {
 274   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
 275   unsigned int eltwordindex;
 276   unsigned int bitindex =   bit % EBITMAP_ELT_BITS;
 277
 278   /* If we have this element cached, just set the bit in it.  */
 279   if (map->cache && map->cacheindex == wordindex)
 280     {
 281       (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
 282       return;
 283     }
 284
 285   /* Resize the wordmask if necessary.  */
 286   if (wordindex >= map->wordmask->n_bits)
 287     map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
 288
 289   /* Allocate a new word in the array and move whatever is in it's
 290      place, if necessary. */
 291   if (!TEST_BIT (map->wordmask, wordindex))
 292     {
 293       unsigned long count;
 294       unsigned int i;
 295
 296       SET_BIT (map->wordmask, wordindex);
 297       count = sbitmap_popcount (map->wordmask, wordindex);
 298       gcc_assert (count <= map->numwords);
 299
 300       for (i = map->numwords; i > count; i--)
 301         {
 302           EBITMAP_ELT_TYPE *newelt;
 303           newelt = ebitmap_array_grow_get (map, i);
 304           *newelt = ebitmap_array_get (map, i - 1);
 305         }
 306       map->numwords++;
 307       eltwordindex = count;
 308       ebitmap_array_maybe_grow (map, eltwordindex);
 309       map->elts[eltwordindex] = 0;
 310     }
 311   else
 312     {
 313       eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
 314     }
 315
 316   /* Set the actual bit.  */
 317   bitindex = bit % EBITMAP_ELT_BITS;
 318
 319   map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
 320   map->cache = &map->elts[eltwordindex];
 321   map->cacheindex = wordindex;
 322 }
 323
 324
 325 /* Return true if MAP contains BIT.  */
 326
 327 bool
 328 ebitmap_bit_p (ebitmap map, unsigned int bit)
 329 {
 330   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
 331   unsigned int bitindex= bit % EBITMAP_ELT_BITS;
 332
 333   /* Trivial empty ebitmap case.  */
 334   if (map->numwords == 0)
 335     return false;
 336
 337   if (map->cache && map->cacheindex == wordindex)
 338     return ((*map->cache) >> bitindex) & 1;
 339
 340   /* If the wordindex is greater than the size of the wordmask, *or*
 341      it's not set in the wordmask, this bit can't exist in our
 342      ebitmap.  */
 343   if (wordindex >= map->wordmask->n_bits
 344       || !TEST_BIT (map->wordmask, wordindex))
 345     return false;
 346
 347   /* Find the bit and test it.  */
 348   map->cacheindex = wordindex;
 349   wordindex = sbitmap_popcount (map->wordmask, wordindex);
 350   map->cache = &map->elts[wordindex];
 351
 352   return (map->elts[wordindex] >> bitindex) & 1;
 353 }
 354
 355 /* Copy ebitmap SRC to DST.  */
 356
 357 void
 358 ebitmap_copy (ebitmap dst, ebitmap src)
 359 {
 360   /* Blow away any existing wordmask, and copy the new one.  */
 361   sbitmap_free (dst->wordmask);
 362   dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
 363   sbitmap_copy (dst->wordmask, src->wordmask);
 364
 365   /* Make sure our destination array is big enough, and then copy the
 366      actual words.  */
 367   ebitmap_array_grow (dst, src->numwords);
 368   memcpy (dst->elts, src->elts,
 369           src->numwords * sizeof (EBITMAP_ELT_TYPE));
 370   dst->numwords = src->numwords;
 371   dst->cache = NULL;
 372 }
 373
 374 /* Dump ebitmap BMAP to FILE.  */
 375
 376 void
 377 dump_ebitmap (FILE *file, ebitmap bmap)
 378 {
 379   unsigned int pos;
 380   unsigned int i;
 381   int res;
 382   unsigned int size;
 383
 384   res = sbitmap_last_set_bit (bmap->wordmask);
 385   if (res == -1)
 386     size = 0;
 387   else
 388     size = (res + 1) * EBITMAP_ELT_BITS;
 389
 390   fprintf (file, "n_words = %d, set = {", bmap->numwords);
 391
 392   for (pos = 30, i = 0; i < size; i++)
 393     if (ebitmap_bit_p (bmap, i))
 394       {
 395         if (pos > 70)
 396           {
 397             fprintf (file, "\n  ");
 398             pos = 0;
 399           }
 400
 401         pos += fprintf (file, "%d ", i);
 402       }
 403
 404   fprintf (file, "}\n");
 405 }
 406
 407 /* Dump ebitmap BMAP to stderr.  */
 408
 409 void
 410 debug_ebitmap (ebitmap bmap)
 411 {
 412   dump_ebitmap (stderr, bmap);
 413 }
 414
 415 /* Perform the operation DST &= SRC.  */
 416
 417 void
 418 ebitmap_and_into (ebitmap dst, ebitmap src)
 419 {
 420   sbitmap_iterator sbi;
 421   unsigned int i;
 422   unsigned int neweltindex = 0;
 423   unsigned int dsteltindex = 0;
 424   unsigned int srceltindex = 0;
 425
 426   gcc_assert (dst != src);
 427
 428   dst->cache = NULL;
 429
 430   /* Short circuit the empty bitmap cases.  */
 431   if (src->numwords == 0 || dst->numwords == 0)
 432     {
 433       ebitmap_clear (dst);
 434       return;
 435     }
 436
 437   /* AND the masks, then walk the words that may actually appear in
 438      the result, AND'ing them.  */
 439   sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
 440
 441   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 442     {
 443       EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
 444       tmpword &= ebitmap_array_get (dst, dsteltindex++);
 445       if (tmpword != 0)
 446         {
 447           EBITMAP_ELT_TYPE *dstplace;
 448           dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 449           *dstplace = tmpword;
 450         }
 451       else
 452         RESET_BIT (dst->wordmask, i);
 453     }
 454 #ifdef EBITMAP_DEBUGGING
 455   {
 456     unsigned int i;
 457
 458     for (i = 0; i <  dst->numwords; i++)
 459       gcc_assert (dst->elts[i] != 0);
 460
 461     verify_popcount (dst->wordmask);
 462     gcc_assert (sbitmap_popcount (dst->wordmask,
 463                                   dst->wordmask->n_bits) == dst->numwords);
 464   }
 465 #endif
 466   dst->numwords = neweltindex;
 467 }
 468
 469 /* Perform the operation DST = SRC1 & SRC2.  */
 470
 471 void
 472 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
 473 {
 474   sbitmap_iterator sbi;
 475   unsigned int i;
 476   unsigned int neweltindex = 0;
 477   unsigned int src1eltindex = 0;
 478   unsigned int src2eltindex = 0;
 479
 480   dst->cache = NULL;
 481   if (src1->numwords == 0 || src2->numwords == 0)
 482     {
 483       ebitmap_clear (dst);
 484       return;
 485     }
 486
 487   dst->wordmask
 488     = sbitmap_resize (dst->wordmask,
 489                       MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
 490                       0);
 491   sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
 492
 493   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 494     {
 495       bool src1hasword, src2hasword;
 496
 497       src1hasword = TEST_BIT (src1->wordmask, i);
 498       src2hasword = TEST_BIT (src2->wordmask, i);
 499
 500       if (src1hasword && src2hasword)
 501         {
 502           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
 503           tmpword &= ebitmap_array_get (src2, src2eltindex++);
 504           if (tmpword != 0)
 505             {
 506               EBITMAP_ELT_TYPE *dstplace;
 507               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 508               *dstplace = tmpword;
 509             }
 510           else
 511             RESET_BIT (dst->wordmask, i);
 512         }
 513       else if (src1hasword)
 514         src1eltindex++;
 515       else
 516         src2eltindex++;
 517     }
 518 #ifdef EBITMAP_DEBUGGING
 519   {
 520     ebitmap_iterator ebi;
 521     unsigned int i;
 522
 523     for (i = 0; i <  dst->numwords; i++)
 524       gcc_assert (dst->elts[i] != 0);
 525
 526     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 527       if (ebitmap_bit_p (src2, i))
 528         gcc_assert (ebitmap_bit_p (dst, i));
 529
 530     for (i = 0; i <  dst->numwords; i++)
 531       gcc_assert (dst->elts[i] != 0);
 532
 533     verify_popcount (dst->wordmask);
 534     gcc_assert (sbitmap_popcount (dst->wordmask,
 535                                   dst->wordmask->n_bits) == dst->numwords);
 536   }
 537 #endif
 538   dst->numwords = neweltindex;
 539 }
 540
 541 /* Perform the operation DST |= SRC.  Return true if any bits in DST
 542    changed.  */
 543
 544 bool
 545 ebitmap_ior_into (ebitmap dst, ebitmap src)
 546 {
 547   unsigned int dstsize = dst->wordmask->n_bits;
 548   unsigned int srcsize = src->wordmask->n_bits;
 549   sbitmap_iterator sbi;
 550   unsigned int i;
 551   sbitmap tempmask;
 552   unsigned int neweltindex = 0;
 553   unsigned int dsteltindex = 0;
 554   unsigned int srceltindex = 0;
 555   bool changed = false;
 556   EBITMAP_ELT_TYPE *newarray;
 557   unsigned int newarraysize;
 558 #ifdef EBITMAP_DEBUGGING
 559   ebitmap dstcopy = ebitmap_alloc (1);
 560   ebitmap_copy (dstcopy, dst);
 561 #endif
 562
 563   dst->cache = NULL;
 564   if (dst == src)
 565     return false;
 566
 567   if (dst->numwords == 0 && src->numwords != 0)
 568     {
 569       ebitmap_copy (dst, src);
 570       return true;
 571     }
 572   else if (src->numwords == 0)
 573     return false;
 574
 575   /* We can do without the temp mask if it's faster, but it would mean
 576      touching more words in the actual dense vector.  */
 577   tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
 578   sbitmap_zero (tempmask);
 579   if (srcsize == dstsize)
 580     {
 581       sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
 582     }
 583   else
 584     {
 585       dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
 586                                       0);
 587       if (srcsize >= dstsize)
 588         {
 589           sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
 590           sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
 591         }
 592       else
 593         {
 594           sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
 595           sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
 596         }
 597     }
 598   newarraysize = src->numwords + dst->numwords;
 599   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 600
 601   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
 602     {
 603       bool dsthasword, srchasword;
 604
 605       dsthasword = (i < dst->wordmask->n_bits
 606                     && TEST_BIT (dst->wordmask, i));
 607       srchasword = (i < src->wordmask->n_bits
 608                     && TEST_BIT (src->wordmask, i));
 609
 610       if (dsthasword && srchasword)
 611         {
 612           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
 613           tmpword |= ebitmap_array_get (dst, dsteltindex);
 614           if (!changed)
 615             changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
 616           dsteltindex++;
 617           newarray[neweltindex++] = tmpword;
 618         }
 619       else if (dsthasword)
 620         {
 621           newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
 622         }
 623       else
 624         {
 625           newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
 626           gcc_assert (i < dst->wordmask->n_bits);
 627           SET_BIT (dst->wordmask, i);
 628           changed |= true;
 629         }
 630     }
 631
 632   sbitmap_free (tempmask);
 633   if (changed)
 634     {
 635       dst->numwords = neweltindex;
 636       free (dst->elts);
 637       dst->elts = newarray;
 638       dst->n_elts = newarraysize;
 639     }
 640   else
 641     free (newarray);
 642
 643 #ifdef EBITMAP_DEBUGGING
 644   {
 645     ebitmap_iterator ebi;
 646     unsigned int i;
 647
 648     for (i = 0; i <  dst->numwords; i++)
 649       gcc_assert (dst->elts[i] != 0);
 650
 651     EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
 652       gcc_assert (ebitmap_bit_p (dst, i));
 653     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
 654       gcc_assert (ebitmap_bit_p (dst, i));
 655
 656     verify_popcount (dst->wordmask);
 657     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 658     gcc_assert (sbitmap_popcount (dst->wordmask,
 659                                   dst->wordmask->n_bits) == dst->numwords);
 660   }
 661 #endif
 662   return changed;
 663 }
 664
 665 /* Perform the operation DST = SRC1 | SRC2.  Return true if any bit
 666    in DST has changed.  */
 667
 668 bool
 669 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
 670 {
 671   unsigned int src1size = src1->wordmask->n_bits;
 672   unsigned int src2size = src2->wordmask->n_bits;
 673   sbitmap_iterator sbi;
 674   unsigned int i;
 675   sbitmap tempmask;
 676   unsigned int neweltindex = 0;
 677   unsigned int src1eltindex = 0;
 678   unsigned int src2eltindex = 0;
 679   bool changed = false;
 680   EBITMAP_ELT_TYPE *newarray;
 681   unsigned int newarraysize;
 682 #ifdef EBITMAP_DEBUGGING
 683   ebitmap dstcopy = ebitmap_alloc (1);
 684   ebitmap_copy (dstcopy, dst);
 685 #endif
 686
 687   dst->cache = NULL;
 688   tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
 689   sbitmap_zero (tempmask);
 690   if (src1size == src2size)
 691     {
 692       sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
 693     }
 694   else
 695     {
 696       if (src1size >= src2size)
 697         {
 698           sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
 699           sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
 700         }
 701       else
 702         {
 703           sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
 704           sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
 705         }
 706     }
 707   newarraysize = src1->numwords + src2->numwords;
 708   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 709
 710   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
 711     {
 712       bool src1hasword, src2hasword;
 713       EBITMAP_ELT_TYPE tmpword;
 714       src1hasword = (i < src1->wordmask->n_bits
 715                     && TEST_BIT (src1->wordmask, i));
 716       src2hasword = (i < src2->wordmask->n_bits
 717                     && TEST_BIT (src2->wordmask, i));
 718
 719       if (src1hasword && src2hasword)
 720         {
 721           tmpword = (ebitmap_array_get (src1, src1eltindex++)
 722                      | ebitmap_array_get (src2, src2eltindex++));
 723           newarray[neweltindex++] = tmpword;
 724         }
 725       else if (src1hasword)
 726         {
 727           tmpword = ebitmap_array_get (src1, src1eltindex++);
 728           newarray [neweltindex++] = tmpword;
 729         }
 730       else
 731         {
 732           tmpword = ebitmap_array_get (src2, src2eltindex++);
 733           newarray [neweltindex++] = tmpword;
 734         }
 735
 736       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
 737         {
 738           changed = true;
 739         }
 740       else if (!changed)
 741         {
 742           unsigned int count = sbitmap_popcount (dst->wordmask, i);
 743           changed |= ebitmap_array_get (dst, count) != tmpword;
 744         }
 745     }
 746
 747   if (changed)
 748     {
 749       sbitmap_free (dst->wordmask);
 750       dst->wordmask = tempmask;
 751       dst->numwords = neweltindex;
 752       free (dst->elts);
 753       dst->elts = newarray;
 754       dst->n_elts = newarraysize;
 755     }
 756   else
 757     {
 758       sbitmap_free (tempmask);
 759       free (newarray);
 760     }
 761
 762 #ifdef EBITMAP_DEBUGGING
 763   {
 764     ebitmap_iterator ebi;
 765     unsigned int i;
 766
 767     for (i = 0; i <  dst->numwords; i++)
 768       gcc_assert (dst->elts[i] != 0);
 769
 770     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 771       gcc_assert (ebitmap_bit_p (dst, i));
 772
 773     EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
 774       gcc_assert (ebitmap_bit_p (dst, i));
 775   }
 776   verify_popcount (dst->wordmask);
 777   gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 778   gcc_assert (sbitmap_popcount (dst->wordmask,
 779                                 dst->wordmask->n_bits) == dst->numwords);
 780 #endif
 781
 782   return changed;
 783 }
 784
 785 /* Perform the operation DST &= ~SRC.  Return true if any bit in DST
 786    has changed.  */
 787
 788 bool
 789 ebitmap_and_compl_into (ebitmap dst, ebitmap src)
 790 {
 791   bool changed = false;
 792   unsigned int i;
 793   unsigned int neweltindex = 0;
 794   unsigned int dsteltindex = 0;
 795   sbitmap_iterator sbi;
 796 #ifdef EBITMAP_DEBUGGING
 797   ebitmap dstcopy = ebitmap_alloc (1);
 798   ebitmap_copy (dstcopy, dst);
 799 #endif
 800
 801   gcc_assert (dst != src);
 802   dst->cache = NULL;
 803   if (src->numwords == 0)
 804     return false;
 805
 806   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 807     {
 808       bool srchasword;
 809
 810       srchasword = (i < src->wordmask->n_bits
 811                     && TEST_BIT (src->wordmask, i));
 812
 813       if (srchasword)
 814         {
 815           unsigned int srccount = sbitmap_popcount (src->wordmask, i);
 816           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
 817           tmpword &= ~(ebitmap_array_get (src, srccount));
 818           if (!changed)
 819             changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
 820           dsteltindex++;
 821           if (tmpword != 0)
 822             {
 823               EBITMAP_ELT_TYPE *dstplace;
 824               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 825               *dstplace = tmpword;
 826             }
 827           else
 828             RESET_BIT (dst->wordmask, i);
 829         }
 830       else
 831         {
 832           dsteltindex++;
 833           neweltindex++;
 834         }
 835     }
 836 #ifdef EBITMAP_DEBUGGING
 837   {
 838     unsigned int i;
 839     ebitmap_iterator ebi;
 840
 841     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
 842       {
 843         if (!ebitmap_bit_p (src, i))
 844           gcc_assert (ebitmap_bit_p (dst, i));
 845       }
 846
 847     for (i = 0; i <  dst->numwords; i++)
 848       gcc_assert (dst->elts[i] != 0);
 849
 850     gcc_assert (sbitmap_popcount (dst->wordmask,
 851                                   dst->wordmask->n_bits) == neweltindex);
 852     verify_popcount (dst->wordmask);
 853     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 854     gcc_assert (sbitmap_popcount (dst->wordmask,
 855                                   dst->wordmask->n_bits) == dst->numwords);
 856   }
 857 #endif
 858   dst->numwords = neweltindex;
 859   /* sbitmap_popcount (dst->wordmask, -1); */
 860
 861   return changed;
 862 }
 863
 864 /* Perform the operation DST = SRC1 & ~SRC2.  Return true if any bit
 865    in DST has changed.  */
 866
 867 bool
 868 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
 869 {
 870   unsigned int src1size = src1->wordmask->n_bits;
 871   sbitmap_iterator sbi;
 872   unsigned int i;
 873   sbitmap tempmask;
 874   unsigned int neweltindex = 0;
 875   unsigned int src1eltindex = 0;
 876   bool changed = false;
 877   EBITMAP_ELT_TYPE *newarray;
 878   unsigned int newarraysize;
 879
 880   /* XXX: Optimize like the into version.  */
 881   dst->cache = NULL;
 882   tempmask = sbitmap_alloc_with_popcount (src1size);
 883   sbitmap_zero (tempmask);
 884   sbitmap_copy (tempmask, src1->wordmask);
 885
 886   newarraysize = src1->numwords;
 887   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 888
 889   EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
 890     {
 891       bool src2hasword;
 892       EBITMAP_ELT_TYPE tmpword;
 893
 894       src2hasword = (i < src2->wordmask->n_bits
 895                      && TEST_BIT (src2->wordmask, i));
 896
 897       if (src2hasword)
 898         {
 899           unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
 900           tmpword = ebitmap_array_get (src1, src1eltindex++)
 901                     & ~(ebitmap_array_get (src2, src2count));
 902           if (tmpword)
 903             {
 904               newarray[neweltindex++] = tmpword;
 905             }
 906           else
 907             RESET_BIT (tempmask, i);
 908
 909         }
 910       else
 911         {
 912           tmpword = ebitmap_array_get (src1, src1eltindex++);
 913           gcc_assert (tmpword != 0);
 914           newarray[neweltindex++] = tmpword;
 915         }
 916
 917       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
 918         {
 919           changed = true;
 920         }
 921       else if (!changed)
 922         {
 923           unsigned int count = sbitmap_popcount (dst->wordmask, i);
 924           changed |= ebitmap_array_get (dst, count) != tmpword;
 925         }
 926     }
 927   if (changed)
 928     {
 929       sbitmap_free (dst->wordmask);
 930       dst->wordmask = tempmask;
 931       dst->numwords = neweltindex;
 932       free (dst->elts);
 933       dst->elts = newarray;
 934       dst->n_elts = newarraysize;
 935     }
 936   else
 937     {
 938       free (tempmask);
 939       free (newarray);
 940     }
 941 #ifdef EBITMAP_DEBUGGING
 942   {
 943     unsigned int i;
 944     ebitmap_iterator ebi;
 945
 946     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 947       {
 948         if (!ebitmap_bit_p (src2, i))
 949           gcc_assert (ebitmap_bit_p (dst, i));
 950       }
 951   for (i = 0; i <  dst->numwords; i++)
 952     gcc_assert (dst->elts[i] != 0);
 953
 954   verify_popcount (dst->wordmask);
 955   gcc_assert (sbitmap_popcount (dst->wordmask,
 956                                 dst->wordmask->n_bits) == dst->numwords);
 957   }
 958 #endif
 959   return changed;
 960 }
 961
 962 /* Perform the operation DST = A | (B & ~C).  */
 963
 964 bool
 965 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
 966 {
 967   bool changed;
 968   ebitmap temp = ebitmap_alloc (1);
 969 #ifdef EBITMAP_DEBUGGING
 970   ebitmap dstcopy = ebitmap_alloc (1);
 971   ebitmap_copy (dstcopy, dst);
 972 #endif
 973
 974   dst->cache = NULL;
 975   ebitmap_and_compl (temp, b, c);
 976   changed = ebitmap_ior (dst, a, temp);
 977 #ifdef EBITMAP_DEBUGGING
 978   {
 979     ebitmap_iterator ebi;
 980     unsigned int i;
 981
 982     EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
 983       gcc_assert (ebitmap_bit_p (dst, i));
 984
 985     EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
 986       if (!ebitmap_bit_p (c, i))
 987         gcc_assert (ebitmap_bit_p (dst, i));
 988     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 989   }
 990 #endif
 991   ebitmap_free (temp);
 992
 993   return changed;
 994 }
 995
 996 /* Return true if ebitmap DST is equal to ebitmap SRC.  */
 997
 998 bool
 999 ebitmap_equal_p (ebitmap dst, ebitmap src)
1000 {
1001   unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1002
1003   if (dst->numwords != src->numwords)
1004     return false;
1005
1006   /* sbitmap_equal compares up to the size of the first argument, so
1007      if the two sbitmaps are not equally sized, we need to pass the
1008      smaller one as the first argument, or it will crash.  */
1009   if (which == dst->wordmask->size
1010       && !sbitmap_equal (dst->wordmask, src->wordmask))
1011     return false;
1012   else if (which == src->wordmask->size
1013            && !sbitmap_equal (src->wordmask, dst->wordmask))
1014     return false;
1015
1016   return memcmp (dst->elts, src->elts,
1017                  dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1018   return true;
1019 }