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 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 = xrealloc (map->elts, sizeof (EBITMAP_ELT_TYPE) * 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 = xmalloc (sizeof (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 = xmalloc (sizeof (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 && map->cacheindex == eltwordindex)
 258         map->cache = NULL;
 259
 260       RESET_BIT (map->wordmask, wordindex);
 261
 262       memmove(&map->elts[eltwordindex], &map->elts[eltwordindex + 1],
 263               sizeof (EBITMAP_ELT_TYPE) * (map->numwords - eltwordindex));
 264       map->numwords--;
 265     }
 266 }
 267
 268 /* Set BIT in ebitmap MAP.  */
 269
 270 void
 271 ebitmap_set_bit (ebitmap map, unsigned int bit)
 272 {
 273   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
 274   unsigned int eltwordindex;
 275   unsigned int bitindex =   bit % EBITMAP_ELT_BITS;
 276
 277   /* If we have this element cached, just set the bit in it.  */
 278   if (map->cache && map->cacheindex == wordindex)
 279     {
 280       (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
 281       return;
 282     }
 283
 284   /* Resize the wordmask if necessary.  */
 285   if (wordindex >= map->wordmask->n_bits)
 286     map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
 287
 288   /* Allocate a new word in the array and move whatever is in it's
 289      place, if necessary. */
 290   if (!TEST_BIT (map->wordmask, wordindex))
 291     {
 292       unsigned long count;
 293       unsigned int i;
 294
 295       SET_BIT (map->wordmask, wordindex);
 296       count = sbitmap_popcount (map->wordmask, wordindex);
 297       gcc_assert (count <= map->numwords);
 298
 299       for (i = map->numwords; i > count; i--)
 300         {
 301           EBITMAP_ELT_TYPE *newelt;
 302           newelt = ebitmap_array_grow_get (map, i);
 303           *newelt = ebitmap_array_get (map, i - 1);
 304         }
 305       map->numwords++;
 306       eltwordindex = count;
 307       ebitmap_array_maybe_grow (map, eltwordindex);
 308       map->elts[eltwordindex] = 0;
 309     }
 310   else
 311     {
 312       eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
 313     }
 314
 315   /* Set the actual bit.  */
 316   bitindex = bit % EBITMAP_ELT_BITS;
 317
 318   map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
 319   map->cache = &map->elts[eltwordindex];
 320   map->cacheindex = wordindex;
 321 }
 322
 323
 324 /* Return true if MAP contains BIT.  */
 325
 326 bool
 327 ebitmap_bit_p (ebitmap map, unsigned int bit)
 328 {
 329   unsigned int wordindex = bit / EBITMAP_ELT_BITS;
 330   unsigned int bitindex= bit % EBITMAP_ELT_BITS;
 331
 332   /* Trivial empty ebitmap case.  */
 333   if (map->numwords == 0)
 334     return false;
 335
 336   if (map->cache && map->cacheindex == wordindex)
 337     return ((*map->cache) >> bitindex) & 1;
 338
 339   /* If the wordindex is greater than the size of the wordmask, *or*
 340      it's not set in the wordmask, this bit can't exist in our
 341      ebitmap.  */
 342   if (wordindex >= map->wordmask->n_bits
 343       || !TEST_BIT (map->wordmask, wordindex))
 344     return false;
 345
 346   /* Find the bit and test it.  */
 347   map->cacheindex = wordindex;
 348   wordindex = sbitmap_popcount (map->wordmask, wordindex);
 349   map->cache = &map->elts[wordindex];
 350
 351   return (map->elts[wordindex] >> bitindex) & 1;
 352 }
 353
 354 /* Copy ebitmap SRC to DST.  */
 355
 356 void
 357 ebitmap_copy (ebitmap dst, ebitmap src)
 358 {
 359   /* Blow away any existing wordmask, and copy the new one.  */
 360   sbitmap_free (dst->wordmask);
 361   dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
 362   sbitmap_copy (dst->wordmask, src->wordmask);
 363
 364   /* Make sure our destination array is big enough, and then copy the
 365      actual words.  */
 366   ebitmap_array_grow (dst, src->numwords);
 367   memcpy (dst->elts, src->elts,
 368           src->numwords * sizeof (EBITMAP_ELT_TYPE));
 369   dst->numwords = src->numwords;
 370   dst->cache = NULL;
 371 }
 372
 373 /* Dump ebitmap BMAP to FILE.  */
 374
 375 void
 376 dump_ebitmap (FILE *file, ebitmap bmap)
 377 {
 378   unsigned int pos;
 379   unsigned int i;
 380   int res;
 381   unsigned int size;
 382
 383   res = sbitmap_last_set_bit (bmap->wordmask);
 384   if (res == -1)
 385     size = 0;
 386   else
 387     size = (res + 1) * EBITMAP_ELT_BITS;
 388
 389   fprintf (file, "n_words = %d, set = {", bmap->numwords);
 390
 391   for (pos = 30, i = 0; i < size; i++)
 392     if (ebitmap_bit_p (bmap, i))
 393       {
 394         if (pos > 70)
 395           {
 396             fprintf (file, "\n  ");
 397             pos = 0;
 398           }
 399
 400         pos += fprintf (file, "%d ", i);
 401       }
 402
 403   fprintf (file, "}\n");
 404 }
 405
 406 /* Dump ebitmap BMAP to stderr.  */
 407
 408 void
 409 debug_ebitmap (ebitmap bmap)
 410 {
 411   dump_ebitmap (stderr, bmap);
 412 }
 413
 414 /* Perform the operation DST &= SRC.  */
 415
 416 void
 417 ebitmap_and_into (ebitmap dst, ebitmap src)
 418 {
 419   sbitmap_iterator sbi;
 420   unsigned int i;
 421   unsigned int neweltindex = 0;
 422   unsigned int dsteltindex = 0;
 423   unsigned int srceltindex = 0;
 424
 425   gcc_assert (dst != src);
 426
 427   dst->cache = NULL;
 428
 429   /* Short circuit the empty bitmap cases.  */
 430   if (src->numwords == 0 || dst->numwords == 0)
 431     {
 432       ebitmap_clear (dst);
 433       return;
 434     }
 435
 436   /* AND the masks, then walk the words that may actually appear in
 437      the result, AND'ing them.  */
 438   sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
 439
 440   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 441     {
 442       EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
 443       tmpword &= ebitmap_array_get (dst, dsteltindex++);
 444       if (tmpword != 0)
 445         {
 446           EBITMAP_ELT_TYPE *dstplace;
 447           dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 448           *dstplace = tmpword;
 449         }
 450       else
 451         RESET_BIT (dst->wordmask, i);
 452     }
 453 #ifdef EBITMAP_DEBUGGING
 454   {
 455     unsigned int i;
 456
 457     for (i = 0; i <  dst->numwords; i++)
 458       gcc_assert (dst->elts[i] != 0);
 459
 460     verify_popcount (dst->wordmask);
 461     gcc_assert (sbitmap_popcount (dst->wordmask,
 462                                   dst->wordmask->n_bits) == dst->numwords);
 463   }
 464 #endif
 465   dst->numwords = neweltindex;
 466 }
 467
 468 /* Perform the operation DST = SRC1 & SRC2.  */
 469
 470 void
 471 ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
 472 {
 473   sbitmap_iterator sbi;
 474   unsigned int i;
 475   unsigned int neweltindex = 0;
 476   unsigned int src1eltindex = 0;
 477   unsigned int src2eltindex = 0;
 478
 479   dst->cache = NULL;
 480   if (src1->numwords == 0 || src2->numwords == 0)
 481     {
 482       ebitmap_clear (dst);
 483       return;
 484     }
 485
 486   dst->wordmask
 487     = sbitmap_resize (dst->wordmask,
 488                       MIN (src1->wordmask->n_bits, src2->wordmask->n_bits),
 489                       0);
 490   sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
 491
 492   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 493     {
 494       bool src1hasword, src2hasword;
 495
 496       src1hasword = TEST_BIT (src1->wordmask, i);
 497       src2hasword = TEST_BIT (src2->wordmask, i);
 498
 499       if (src1hasword && src2hasword)
 500         {
 501           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
 502           tmpword &= ebitmap_array_get (src2, src2eltindex++);
 503           if (tmpword != 0)
 504             {
 505               EBITMAP_ELT_TYPE *dstplace;
 506               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 507               *dstplace = tmpword;
 508             }
 509           else
 510             RESET_BIT (dst->wordmask, i);
 511         }
 512       else if (src1hasword)
 513         src1eltindex++;
 514       else
 515         src2eltindex++;
 516     }
 517 #ifdef EBITMAP_DEBUGGING
 518   {
 519     ebitmap_iterator ebi;
 520     unsigned int i;
 521
 522     for (i = 0; i <  dst->numwords; i++)
 523       gcc_assert (dst->elts[i] != 0);
 524
 525     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 526       if (ebitmap_bit_p (src2, i))
 527         gcc_assert (ebitmap_bit_p (dst, i));
 528
 529     for (i = 0; i <  dst->numwords; i++)
 530       gcc_assert (dst->elts[i] != 0);
 531
 532     verify_popcount (dst->wordmask);
 533     gcc_assert (sbitmap_popcount (dst->wordmask,
 534                                   dst->wordmask->n_bits) == dst->numwords);
 535   }
 536 #endif
 537   dst->numwords = neweltindex;
 538 }
 539
 540 /* Perform the operation DST |= SRC.  Return true if any bits in DST
 541    changed.  */
 542
 543 bool
 544 ebitmap_ior_into (ebitmap dst, ebitmap src)
 545 {
 546   unsigned int dstsize = dst->wordmask->n_bits;
 547   unsigned int srcsize = src->wordmask->n_bits;
 548   sbitmap_iterator sbi;
 549   unsigned int i;
 550   sbitmap tempmask;
 551   unsigned int neweltindex = 0;
 552   unsigned int dsteltindex = 0;
 553   unsigned int srceltindex = 0;
 554   bool changed = false;
 555   EBITMAP_ELT_TYPE *newarray;
 556   unsigned int newarraysize;
 557 #ifdef EBITMAP_DEBUGGING
 558   ebitmap dstcopy = ebitmap_alloc (1);
 559   ebitmap_copy (dstcopy, dst);
 560 #endif
 561
 562   dst->cache = NULL;
 563   if (dst == src)
 564     return false;
 565
 566   if (dst->numwords == 0 && src->numwords != 0)
 567     {
 568       ebitmap_copy (dst, src);
 569       return true;
 570     }
 571   else if (src->numwords == 0)
 572     return false;
 573
 574   /* We can do without the temp mask if it's faster, but it would mean
 575      touching more words in the actual dense vector.  */
 576   tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
 577   sbitmap_zero (tempmask);
 578   if (srcsize == dstsize)
 579     {
 580       sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
 581     }
 582   else
 583     {
 584       dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
 585                                       0);
 586       if (srcsize >= dstsize)
 587         {
 588           sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
 589           sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
 590         }
 591       else
 592         {
 593           sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
 594           sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
 595         }
 596     }
 597   newarraysize = src->numwords + dst->numwords;
 598   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 599
 600   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
 601     {
 602       bool dsthasword, srchasword;
 603
 604       dsthasword = (i < dst->wordmask->n_bits
 605                     && TEST_BIT (dst->wordmask, i));
 606       srchasword = (i < src->wordmask->n_bits
 607                     && TEST_BIT (src->wordmask, i));
 608
 609       if (dsthasword && srchasword)
 610         {
 611           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
 612           tmpword |= ebitmap_array_get (dst, dsteltindex);
 613           if (!changed)
 614             changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
 615           dsteltindex++;
 616           newarray[neweltindex++] = tmpword;
 617         }
 618       else if (dsthasword)
 619         {
 620           newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
 621         }
 622       else
 623         {
 624           newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
 625           gcc_assert (i < dst->wordmask->n_bits);
 626           SET_BIT (dst->wordmask, i);
 627           changed |= true;
 628         }
 629     }
 630
 631   sbitmap_free (tempmask);
 632   if (changed)
 633     {
 634       dst->numwords = neweltindex;
 635       free (dst->elts);
 636       dst->elts = newarray;
 637       dst->n_elts = newarraysize;
 638     }
 639   else
 640     free (newarray);
 641
 642 #ifdef EBITMAP_DEBUGGING
 643   {
 644     ebitmap_iterator ebi;
 645     unsigned int i;
 646
 647     for (i = 0; i <  dst->numwords; i++)
 648       gcc_assert (dst->elts[i] != 0);
 649
 650     EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
 651       gcc_assert (ebitmap_bit_p (dst, i));
 652     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
 653       gcc_assert (ebitmap_bit_p (dst, i));
 654
 655     verify_popcount (dst->wordmask);
 656     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 657     gcc_assert (sbitmap_popcount (dst->wordmask,
 658                                   dst->wordmask->n_bits) == dst->numwords);
 659   }
 660 #endif
 661   return changed;
 662 }
 663
 664 /* Perform the operation DST = SRC1 | SRC2.  Return true if any bit
 665    in DST has changed.  */
 666
 667 bool
 668 ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
 669 {
 670   unsigned int src1size = src1->wordmask->n_bits;
 671   unsigned int src2size = src2->wordmask->n_bits;
 672   sbitmap_iterator sbi;
 673   unsigned int i;
 674   sbitmap tempmask;
 675   unsigned int neweltindex = 0;
 676   unsigned int src1eltindex = 0;
 677   unsigned int src2eltindex = 0;
 678   bool changed = false;
 679   EBITMAP_ELT_TYPE *newarray;
 680   unsigned int newarraysize;
 681 #ifdef EBITMAP_DEBUGGING
 682   ebitmap dstcopy = ebitmap_alloc (1);
 683   ebitmap_copy (dstcopy, dst);
 684 #endif
 685
 686   dst->cache = NULL;
 687   tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
 688   sbitmap_zero (tempmask);
 689   if (src1size == src2size)
 690     {
 691       sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
 692     }
 693   else
 694     {
 695       if (src1size >= src2size)
 696         {
 697           sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
 698           sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
 699         }
 700       else
 701         {
 702           sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
 703           sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
 704         }
 705     }
 706   newarraysize = src1->numwords + src2->numwords;
 707   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 708
 709   EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
 710     {
 711       bool src1hasword, src2hasword;
 712       EBITMAP_ELT_TYPE tmpword;
 713       src1hasword = (i < src1->wordmask->n_bits
 714                     && TEST_BIT (src1->wordmask, i));
 715       src2hasword = (i < src2->wordmask->n_bits
 716                     && TEST_BIT (src2->wordmask, i));
 717
 718       if (src1hasword && src2hasword)
 719         {
 720           tmpword = (ebitmap_array_get (src1, src1eltindex++)
 721                      | ebitmap_array_get (src2, src2eltindex++));
 722           newarray[neweltindex++] = tmpword;
 723         }
 724       else if (src1hasword)
 725         {
 726           tmpword = ebitmap_array_get (src1, src1eltindex++);
 727           newarray [neweltindex++] = tmpword;
 728         }
 729       else
 730         {
 731           tmpword = ebitmap_array_get (src2, src2eltindex++);
 732           newarray [neweltindex++] = tmpword;
 733         }
 734
 735       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
 736         {
 737           changed = true;
 738         }
 739       else if (!changed)
 740         {
 741           unsigned int count = sbitmap_popcount (dst->wordmask, i);
 742           changed |= ebitmap_array_get (dst, count) != tmpword;
 743         }
 744     }
 745
 746   if (changed)
 747     {
 748       sbitmap_free (dst->wordmask);
 749       dst->wordmask = tempmask;
 750       dst->numwords = neweltindex;
 751       free (dst->elts);
 752       dst->elts = newarray;
 753       dst->n_elts = newarraysize;
 754     }
 755   else
 756     {
 757       sbitmap_free (tempmask);
 758       free (newarray);
 759     }
 760
 761 #ifdef EBITMAP_DEBUGGING
 762   {
 763     ebitmap_iterator ebi;
 764     unsigned int i;
 765
 766     for (i = 0; i <  dst->numwords; i++)
 767       gcc_assert (dst->elts[i] != 0);
 768
 769     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 770       gcc_assert (ebitmap_bit_p (dst, i));
 771
 772     EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
 773       gcc_assert (ebitmap_bit_p (dst, i));
 774   }
 775   verify_popcount (dst->wordmask);
 776   gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 777   gcc_assert (sbitmap_popcount (dst->wordmask,
 778                                 dst->wordmask->n_bits) == dst->numwords);
 779 #endif
 780
 781   return changed;
 782 }
 783
 784 /* Perform the operation DST &= ~SRC.  Return true if any bit in DST
 785    has changed.  */
 786
 787 bool
 788 ebitmap_and_compl_into (ebitmap dst, ebitmap src)
 789 {
 790   bool changed = false;
 791   unsigned int i;
 792   unsigned int neweltindex = 0;
 793   unsigned int dsteltindex = 0;
 794   sbitmap_iterator sbi;
 795 #ifdef EBITMAP_DEBUGGING
 796   ebitmap dstcopy = ebitmap_alloc (1);
 797   ebitmap_copy (dstcopy, dst);
 798 #endif
 799
 800   gcc_assert (dst != src);
 801   dst->cache = NULL;
 802   if (src->numwords == 0)
 803     return false;
 804
 805   EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
 806     {
 807       bool srchasword;
 808
 809       srchasword = (i < src->wordmask->n_bits
 810                     && TEST_BIT (src->wordmask, i));
 811
 812       if (srchasword)
 813         {
 814           unsigned int srccount = sbitmap_popcount (src->wordmask, i);
 815           EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
 816           tmpword &= ~(ebitmap_array_get (src, srccount));
 817           if (!changed)
 818             changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
 819           dsteltindex++;
 820           if (tmpword != 0)
 821             {
 822               EBITMAP_ELT_TYPE *dstplace;
 823               dstplace = ebitmap_array_grow_get (dst, neweltindex++);
 824               *dstplace = tmpword;
 825             }
 826           else
 827             RESET_BIT (dst->wordmask, i);
 828         }
 829       else
 830         {
 831           dsteltindex++;
 832           neweltindex++;
 833         }
 834     }
 835 #ifdef EBITMAP_DEBUGGING
 836   {
 837     unsigned int i;
 838     ebitmap_iterator ebi;
 839
 840     EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
 841       {
 842         if (!ebitmap_bit_p (src, i))
 843           gcc_assert (ebitmap_bit_p (dst, i));
 844       }
 845
 846     for (i = 0; i <  dst->numwords; i++)
 847       gcc_assert (dst->elts[i] != 0);
 848
 849     gcc_assert (sbitmap_popcount (dst->wordmask,
 850                                   dst->wordmask->n_bits) == neweltindex);
 851     verify_popcount (dst->wordmask);
 852     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 853     gcc_assert (sbitmap_popcount (dst->wordmask,
 854                                   dst->wordmask->n_bits) == dst->numwords);
 855   }
 856 #endif
 857   dst->numwords = neweltindex;
 858   /* sbitmap_popcount (dst->wordmask, -1); */
 859
 860   return changed;
 861 }
 862
 863 /* Perform the operation DST = SRC1 & ~SRC2.  Return true if any bit
 864    in DST has changed.  */
 865
 866 bool
 867 ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
 868 {
 869   unsigned int src1size = src1->wordmask->n_bits;
 870   sbitmap_iterator sbi;
 871   unsigned int i;
 872   sbitmap tempmask;
 873   unsigned int neweltindex = 0;
 874   unsigned int src1eltindex = 0;
 875   bool changed = false;
 876   EBITMAP_ELT_TYPE *newarray;
 877   unsigned int newarraysize;
 878
 879   /* XXX: Optimize like the into version.  */
 880   dst->cache = NULL;
 881   tempmask = sbitmap_alloc_with_popcount (src1size);
 882   sbitmap_zero (tempmask);
 883   sbitmap_copy (tempmask, src1->wordmask);
 884
 885   newarraysize = src1->numwords;
 886   newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
 887
 888   EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
 889     {
 890       bool src2hasword;
 891       EBITMAP_ELT_TYPE tmpword;
 892
 893       src2hasword = (i < src2->wordmask->n_bits
 894                      && TEST_BIT (src2->wordmask, i));
 895
 896       if (src2hasword)
 897         {
 898           unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
 899           tmpword = ebitmap_array_get (src1, src1eltindex++)
 900                     & ~(ebitmap_array_get (src2, src2count));
 901           if (tmpword)
 902             {
 903               newarray[neweltindex++] = tmpword;
 904             }
 905           else
 906             RESET_BIT (tempmask, i);
 907
 908         }
 909       else
 910         {
 911           tmpword = ebitmap_array_get (src1, src1eltindex++);
 912           gcc_assert (tmpword != 0);
 913           newarray[neweltindex++] = tmpword;
 914         }
 915
 916       if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
 917         {
 918           changed = true;
 919         }
 920       else if (!changed)
 921         {
 922           unsigned int count = sbitmap_popcount (dst->wordmask, i);
 923           changed |= ebitmap_array_get (dst, count) != tmpword;
 924         }
 925     }
 926   if (changed)
 927     {
 928       sbitmap_free (dst->wordmask);
 929       dst->wordmask = tempmask;
 930       dst->numwords = neweltindex;
 931       free (dst->elts);
 932       dst->elts = newarray;
 933       dst->n_elts = newarraysize;
 934     }
 935   else
 936     {
 937       free (tempmask);
 938       free (newarray);
 939     }
 940 #ifdef EBITMAP_DEBUGGING
 941   {
 942     unsigned int i;
 943     ebitmap_iterator ebi;
 944
 945     EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
 946       {
 947         if (!ebitmap_bit_p (src2, i))
 948           gcc_assert (ebitmap_bit_p (dst, i));
 949       }
 950   for (i = 0; i <  dst->numwords; i++)
 951     gcc_assert (dst->elts[i] != 0);
 952
 953   verify_popcount (dst->wordmask);
 954   gcc_assert (sbitmap_popcount (dst->wordmask,
 955                                 dst->wordmask->n_bits) == dst->numwords);
 956   }
 957 #endif
 958   return changed;
 959 }
 960
 961 /* Perform the operation DST = A | (B & ~C).  */
 962
 963 bool
 964 ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
 965 {
 966   bool changed;
 967   ebitmap temp = ebitmap_alloc (1);
 968 #ifdef EBITMAP_DEBUGGING
 969   ebitmap dstcopy = ebitmap_alloc (1);
 970   ebitmap_copy (dstcopy, dst);
 971 #endif
 972
 973   dst->cache = NULL;
 974   ebitmap_and_compl (temp, b, c);
 975   changed = ebitmap_ior (dst, a, temp);
 976 #ifdef EBITMAP_DEBUGGING
 977   {
 978     ebitmap_iterator ebi;
 979     unsigned int i;
 980
 981     EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
 982       gcc_assert (ebitmap_bit_p (dst, i));
 983
 984     EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
 985       if (!ebitmap_bit_p (c, i))
 986         gcc_assert (ebitmap_bit_p (dst, i));
 987     gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
 988   }
 989 #endif
 990   ebitmap_free (temp);
 991
 992   return changed;
 993 }
 994
 995 /* Return true if ebitmap DST is equal to ebitmap SRC.  */
 996
 997 bool
 998 ebitmap_equal_p (ebitmap dst, ebitmap src)
 999 {
1000   unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
1001
1002   if (dst->numwords != src->numwords)
1003     return false;
1004
1005   /* sbitmap_equal compares up to the size of the first argument, so
1006      if the two sbitmaps are not equally sized, we need to pass the
1007      smaller one as the first argument, or it will crash.  */
1008   if (which == dst->wordmask->size
1009       && !sbitmap_equal (dst->wordmask, src->wordmask))
1010     return false;
1011   else if (which == src->wordmask->size
1012            && !sbitmap_equal (src->wordmask, dst->wordmask))
1013     return false;
1014
1015   return memcmp (dst->elts, src->elts,
1016                  dst->numwords * sizeof (EBITMAP_ELT_TYPE)) == 0;
1017   return true;
1018 }