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 "ebitmap.h" 25 26 /* The ebitmap data structure is a sparse bitmap structure that works 27 by having two pieces: 28 1. An array of all nonzero words in the structures, organized as 29 an array of HOST_WIDE_INT's. 30 2. A non-sparse bitmap saying which bitmap words are present in the 31 array. 32 33 As a consequence of this representation, testing whether a bit 34 exists in the bitmap is faster than linked-list bitmaps. For bits 35 in words that are all zero, the time to test is O(1). For bits in 36 words that exist, it requires O(n/sizeof(word)) time to perform the 37 test (ignoring the one element cache). It also has much better 38 locality than linked-list bitmaps. 39 40 To test whether a bit exists, we do the following: 41 1. Test whether the word the bit would appear in exists in the 42 bitmap (O(1) check of the mask). If not, fail. 43 44 2. Population count the mask up to the word containing the bit, to 45 find the place in the array the word would be (popcount is cached, 46 but this is just as slow as the linked-list bitmap) 47 3. Test the word to see if the bit exists. 48 49 Just like linked-list bitmaps, we cache the last element that has 50 been tested in order to speed up common access patterns. 51 52 Most of the other speedups are simply due to better locality of the 53 single contiguous array. 54 55 As would be expected in a structure like this, insertion into an 56 empty word in the middle requires moving bits to make room for the 57 new word. As most operations that perform sets perform them in 58 order, this is rarely a problem. We also take advantage of the 59 same element cache to make repeated sets to the same word O(1). 60 61 Operations on the entire bitmap are also more efficient than linked 62 list bitmaps, as they are all operating on contiguous memory, and 63 can be easily vectorized. They are all O(number of words) + 64 O(number of bits that may end up in the destination), as the 65 appropriate operation is first performed on the word mask, and then 66 only those elements that may generate results are touched. 67 68 Memory wise, the ebitmap starts out using less memory than the 69 linked-list bitmap, but its size in memory is technically bounded 70 by ((index of the highest bit set) / (size of a word) + (index of 71 the highest bit set) / ((size of a word) * (size of a word))) This 72 is because the mask is non-sparse. The mask could be transformed 73 into a sparse bitmap at the cost of making bit testing 74 *theoretically* slower (real world numbers have not been computed 75 yet as to whether it matters or not). */ 76 77 /* #define EBITMAP_DEBUGGING */ 78 79 /* Find the last set bit in ebitmap MAP. */ 80 81 int 82 ebitmap_last_set_bit (ebitmap map) 83 { 84 unsigned int i = 0; 85 ebitmap_iterator ebi; 86 bool foundbit = false; 87 88 /* This is not the fastest way to do this, we could simply look for 89 the popcount, and start there, but this function is not used 90 anywhere speed critical. */ 91 EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi) 92 { 93 foundbit = true; 94 } 95 96 97 if (foundbit) 98 return i; 99 return -1; 100 } 101 102 /* Grow or shrink the internal word array for MAP to NEWSIZE 103 elements. */ 104 105 static inline void 106 ebitmap_array_grow (ebitmap map, unsigned int newsize) 107 { 108 if (newsize <= map->n_elts) 109 { 110 map->n_elts = newsize; 111 return; 112 } 113 114 newsize += newsize / 4; 115 116 map->n_elts = newsize; 117 map->elts = XRESIZEVEC (EBITMAP_ELT_TYPE, map->elts, newsize); 118 } 119 120 /* Grow the internal word array for MAP so it is at least SIZE 121 elements. Will not shrink the array if it is already big 122 enough. */ 123 124 static inline void 125 ebitmap_array_maybe_grow (ebitmap map, unsigned int size) 126 { 127 if (size >= map->n_elts) 128 ebitmap_array_grow (map, size + 1); 129 } 130 131 /* Retrieve the IDX'th element from the word array for MAP. */ 132 133 static inline EBITMAP_ELT_TYPE 134 ebitmap_array_get (ebitmap map, unsigned int idx) 135 { 136 gcc_assert (idx < map->n_elts); 137 return map->elts[idx]; 138 } 139 140 /* Retrieve a pointer to the IDX'th element from the word array for 141 MAP. If the element index is greater than the size of the array, 142 the array will be grown to the correct size. */ 143 144 static inline EBITMAP_ELT_TYPE * 145 ebitmap_array_grow_get (ebitmap map, unsigned int idx) 146 { 147 if (idx >= map->n_elts) 148 ebitmap_array_grow (map, idx + 1); 149 return &map->elts[idx]; 150 } 151 152 /* Initialize the internal word array for MAP, so that it is SIZE 153 elements. */ 154 155 static inline void 156 ebitmap_array_init (ebitmap map, unsigned int size) 157 { 158 if (size > 0) 159 { 160 map->elts = XNEWVEC (EBITMAP_ELT_TYPE, size); 161 map->n_elts = size; 162 } 163 else 164 { 165 map->n_elts = 0; 166 map->elts = NULL; 167 } 168 } 169 170 /* Free the internal word array for MAP. */ 171 172 static inline void 173 ebitmap_array_clear (ebitmap map) 174 { 175 if (map->elts) 176 { 177 free (map->elts); 178 map->elts = NULL; 179 } 180 map->n_elts = 0; 181 } 182 183 /* Clear ebitmap MAP. */ 184 185 void 186 ebitmap_clear (ebitmap map) 187 { 188 ebitmap_array_clear (map); 189 sbitmap_zero (map->wordmask); 190 map->wordmask = sbitmap_resize (map->wordmask, 1, 0); 191 map->numwords = 0; 192 map->cache = NULL; 193 map->cacheindex = 0; 194 } 195 196 /* Allocate an ebitmap with enough room for SIZE bits to start out. */ 197 198 ebitmap 199 ebitmap_alloc (unsigned int size) 200 { 201 ebitmap ret = XNEW (struct ebitmap_def); 202 if (size == 0) 203 size = EBITMAP_ELT_BITS; 204 ebitmap_array_init (ret, (size + EBITMAP_ELT_BITS - 1) / EBITMAP_ELT_BITS); 205 ret->wordmask = sbitmap_alloc_with_popcount (size); 206 sbitmap_zero (ret->wordmask); 207 ret->numwords = 0; 208 ret->cache = NULL; 209 ret->cacheindex = 0; 210 211 return ret; 212 } 213 214 /* Clear BIT from ebitmap MAP. */ 215 216 void 217 ebitmap_clear_bit (ebitmap map, unsigned int bit) 218 { 219 unsigned int wordindex = bit / EBITMAP_ELT_BITS; 220 unsigned int eltwordindex = 0; 221 unsigned int bitindex, shift; 222 bool have_eltwordindex = false; 223 EBITMAP_ELT_TYPE *elt_ptr; 224 225 /* If the bit can't exist in our bitmap, just return. */ 226 if (map->numwords == 0) 227 return; 228 229 if (wordindex >= map->wordmask->n_bits 230 || !TEST_BIT (map->wordmask, wordindex)) 231 return; 232 233 if (map->cache != NULL && map->cacheindex == wordindex) 234 elt_ptr = map->cache; 235 else 236 { 237 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); 238 elt_ptr = &map->elts[eltwordindex]; 239 have_eltwordindex = true; 240 } 241 242 bitindex = bit % EBITMAP_ELT_BITS; 243 shift = bitindex; 244 245 *(elt_ptr) &= ~(((EBITMAP_ELT_TYPE)1) << shift); 246 247 /* Clear out the empty words. */ 248 if (*(elt_ptr) == 0) 249 { 250 if (!have_eltwordindex) 251 eltwordindex = sbitmap_popcount (map->wordmask, wordindex); 252 253 if (map->cache != NULL) 254 { 255 if (map->cacheindex == wordindex) 256 map->cache = NULL; 257 else if (map->cacheindex > wordindex) 258 map->cache = map->cache - 1; 259 } 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 DEBUG_FUNCTION 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 sbitmap_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 sbitmap_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 = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); 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 sbitmap_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 = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); 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 sbitmap_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 sbitmap_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 = XNEWVEC (EBITMAP_ELT_TYPE, newarraysize); 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 sbitmap_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 } 1020