gcc/ebitmap.c

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