1/* Simple bitmaps. 2 Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008 3 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 "hard-reg-set.h" 28#include "obstack.h" 29#include "basic-block.h" 30 31#if GCC_VERSION >= 3400 32#if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG 33#define do_popcount(x) __builtin_popcountl(x) 34#elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG 35#define do_popcount(x) __builtin_popcountll(x) 36#else 37#error "internal error: sbitmap.h and hwint.h are inconsistent" 38#endif 39#else 40static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE); 41#define do_popcount(x) sbitmap_elt_popcount((x)) 42#endif 43 44/* This macro controls debugging that is as expensive as the 45 operations it verifies. */ 46 47/* #define BITMAP_DEBUGGING */ 48#ifdef BITMAP_DEBUGGING 49 50/* Verify the population count of sbitmap A matches the cached value, 51 if there is a cached value. */ 52 53void 54sbitmap_verify_popcount (const_sbitmap a) 55{ 56 unsigned ix; 57 unsigned int lastword; 58 59 if (!a->popcount) 60 return; 61 62 lastword = a->size; 63 for (ix = 0; ix < lastword; ix++) 64 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix])); 65} 66#endif 67 68/* Bitmap manipulation routines. */ 69 70/* Allocate a simple bitmap of N_ELMS bits. */ 71 72sbitmap 73sbitmap_alloc (unsigned int n_elms) 74{ 75 unsigned int bytes, size, amt; 76 sbitmap bmap; 77 78 size = SBITMAP_SET_SIZE (n_elms); 79 bytes = size * sizeof (SBITMAP_ELT_TYPE); 80 amt = (sizeof (struct simple_bitmap_def) 81 + bytes - sizeof (SBITMAP_ELT_TYPE)); 82 bmap = (sbitmap) xmalloc (amt); 83 bmap->n_bits = n_elms; 84 bmap->size = size; 85 bmap->popcount = NULL; 86 return bmap; 87} 88 89/* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */ 90 91sbitmap 92sbitmap_alloc_with_popcount (unsigned int n_elms) 93{ 94 sbitmap const bmap = sbitmap_alloc (n_elms); 95 bmap->popcount = XNEWVEC (unsigned char, bmap->size); 96 return bmap; 97} 98 99/* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the 100 size of BMAP, clear the new bits to zero if the DEF argument 101 is zero, and set them to one otherwise. */ 102 103sbitmap 104sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) 105{ 106 unsigned int bytes, size, amt; 107 unsigned int last_bit; 108 109 size = SBITMAP_SET_SIZE (n_elms); 110 bytes = size * sizeof (SBITMAP_ELT_TYPE); 111 if (bytes > SBITMAP_SIZE_BYTES (bmap)) 112 { 113 amt = (sizeof (struct simple_bitmap_def) 114 + bytes - sizeof (SBITMAP_ELT_TYPE)); 115 bmap = (sbitmap) xrealloc (bmap, amt); 116 if (bmap->popcount) 117 bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size); 118 } 119 120 if (n_elms > bmap->n_bits) 121 { 122 if (def) 123 { 124 memset (bmap->elms + bmap->size, -1, 125 bytes - SBITMAP_SIZE_BYTES (bmap)); 126 127 /* Set the new bits if the original last element. */ 128 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 129 if (last_bit) 130 bmap->elms[bmap->size - 1] 131 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 132 133 /* Clear the unused bit in the new last element. */ 134 last_bit = n_elms % SBITMAP_ELT_BITS; 135 if (last_bit) 136 bmap->elms[size - 1] 137 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 138 } 139 else 140 { 141 memset (bmap->elms + bmap->size, 0, 142 bytes - SBITMAP_SIZE_BYTES (bmap)); 143 if (bmap->popcount) 144 memset (bmap->popcount + bmap->size, 0, 145 (size * sizeof (unsigned char)) 146 - (bmap->size * sizeof (unsigned char))); 147 148 } 149 } 150 else if (n_elms < bmap->n_bits) 151 { 152 /* Clear the surplus bits in the last word. */ 153 last_bit = n_elms % SBITMAP_ELT_BITS; 154 if (last_bit) 155 { 156 bmap->elms[size - 1] 157 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 158 if (bmap->popcount) 159 bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]); 160 } 161 } 162 163 bmap->n_bits = n_elms; 164 bmap->size = size; 165 return bmap; 166} 167 168/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */ 169 170sbitmap 171sbitmap_realloc (sbitmap src, unsigned int n_elms) 172{ 173 unsigned int bytes, size, amt; 174 sbitmap bmap; 175 176 size = SBITMAP_SET_SIZE (n_elms); 177 bytes = size * sizeof (SBITMAP_ELT_TYPE); 178 amt = (sizeof (struct simple_bitmap_def) 179 + bytes - sizeof (SBITMAP_ELT_TYPE)); 180 181 if (SBITMAP_SIZE_BYTES (src) >= bytes) 182 { 183 src->n_bits = n_elms; 184 return src; 185 } 186 187 bmap = (sbitmap) xrealloc (src, amt); 188 bmap->n_bits = n_elms; 189 bmap->size = size; 190 return bmap; 191} 192 193/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 194 195sbitmap * 196sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) 197{ 198 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 199 sbitmap *bitmap_vector; 200 201 size = SBITMAP_SET_SIZE (n_elms); 202 bytes = size * sizeof (SBITMAP_ELT_TYPE); 203 elm_bytes = (sizeof (struct simple_bitmap_def) 204 + bytes - sizeof (SBITMAP_ELT_TYPE)); 205 vector_bytes = n_vecs * sizeof (sbitmap *); 206 207 /* Round up `vector_bytes' to account for the alignment requirements 208 of an sbitmap. One could allocate the vector-table and set of sbitmaps 209 separately, but that requires maintaining two pointers or creating 210 a cover struct to hold both pointers (so our result is still just 211 one pointer). Neither is a bad idea, but this is simpler for now. */ 212 { 213 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 214 struct { char x; SBITMAP_ELT_TYPE y; } align; 215 int alignment = (char *) & align.y - & align.x; 216 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 217 } 218 219 amt = vector_bytes + (n_vecs * elm_bytes); 220 bitmap_vector = (sbitmap *) xmalloc (amt); 221 222 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 223 { 224 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 225 226 bitmap_vector[i] = b; 227 b->n_bits = n_elms; 228 b->size = size; 229 b->popcount = NULL; 230 } 231 232 return bitmap_vector; 233} 234 235/* Copy sbitmap SRC to DST. */ 236 237void 238sbitmap_copy (sbitmap dst, const_sbitmap src) 239{ 240 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 241 if (dst->popcount) 242 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size); 243} 244 245/* Copy the first N elements of sbitmap SRC to DST. */ 246 247void 248sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n) 249{ 250 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n); 251 if (dst->popcount) 252 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n); 253} 254 255/* Determine if a == b. */ 256int 257sbitmap_equal (const_sbitmap a, const_sbitmap b) 258{ 259 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 260} 261 262/* Return true if the bitmap is empty. */ 263 264bool 265sbitmap_empty_p (const_sbitmap bmap) 266{ 267 unsigned int i; 268 for (i=0; i<bmap->size; i++) 269 if (bmap->elms[i]) 270 return false; 271 272 return true; 273} 274 275/* Return false if any of the N bits are set in MAP starting at 276 START. */ 277 278bool 279sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n) 280{ 281 unsigned int i = start / SBITMAP_ELT_BITS; 282 SBITMAP_ELT_TYPE elm; 283 unsigned int shift = start % SBITMAP_ELT_BITS; 284 285 gcc_assert (bmap->n_bits >= start + n); 286 287 elm = bmap->elms[i]; 288 elm = elm >> shift; 289 290 if (shift + n <= SBITMAP_ELT_BITS) 291 { 292 /* The bits are totally contained in a single element. */ 293 if (shift + n < SBITMAP_ELT_BITS) 294 elm &= ((1 << n) - 1); 295 return (elm == 0); 296 } 297 298 if (elm) 299 return false; 300 301 n -= SBITMAP_ELT_BITS - shift; 302 i++; 303 304 /* Deal with full elts. */ 305 while (n >= SBITMAP_ELT_BITS) 306 { 307 if (bmap->elms[i]) 308 return false; 309 i++; 310 n -= SBITMAP_ELT_BITS; 311 } 312 313 /* The leftover bits. */ 314 if (n) 315 { 316 elm = bmap->elms[i]; 317 elm &= ((1 << n) - 1); 318 return (elm == 0); 319 } 320 321 return true; 322} 323 324 325 326/* Zero all elements in a bitmap. */ 327 328void 329sbitmap_zero (sbitmap bmap) 330{ 331 memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap)); 332 if (bmap->popcount) 333 memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char)); 334} 335 336/* Set all elements in a bitmap to ones. */ 337 338void 339sbitmap_ones (sbitmap bmap) 340{ 341 unsigned int last_bit; 342 343 memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap)); 344 if (bmap->popcount) 345 memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char)); 346 347 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 348 if (last_bit) 349 { 350 bmap->elms[bmap->size - 1] 351 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 352 if (bmap->popcount) 353 bmap->popcount[bmap->size - 1] 354 = do_popcount (bmap->elms[bmap->size - 1]); 355 } 356} 357 358/* Zero a vector of N_VECS bitmaps. */ 359 360void 361sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs) 362{ 363 unsigned int i; 364 365 for (i = 0; i < n_vecs; i++) 366 sbitmap_zero (bmap[i]); 367} 368 369/* Set a vector of N_VECS bitmaps to ones. */ 370 371void 372sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) 373{ 374 unsigned int i; 375 376 for (i = 0; i < n_vecs; i++) 377 sbitmap_ones (bmap[i]); 378} 379 380/* Set DST to be A union (B - C). 381 DST = A | (B & ~C). 382 Returns true if any change is made. */ 383 384bool 385sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 386{ 387 unsigned int i, n = dst->size; 388 sbitmap_ptr dstp = dst->elms; 389 const_sbitmap_ptr ap = a->elms; 390 const_sbitmap_ptr bp = b->elms; 391 const_sbitmap_ptr cp = c->elms; 392 SBITMAP_ELT_TYPE changed = 0; 393 394 gcc_assert (!dst->popcount); 395 396 for (i = 0; i < n; i++) 397 { 398 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 399 changed |= *dstp ^ tmp; 400 *dstp++ = tmp; 401 } 402 403 return changed != 0; 404} 405 406void 407sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 408{ 409 unsigned int i, n = dst->size; 410 sbitmap_ptr dstp = dst->elms; 411 const_sbitmap_ptr ap = a->elms; 412 const_sbitmap_ptr bp = b->elms; 413 const_sbitmap_ptr cp = c->elms; 414 415 gcc_assert (!dst->popcount && !a->popcount 416 && !b->popcount && !c->popcount); 417 418 for (i = 0; i < n; i++) 419 *dstp++ = *ap++ | (*bp++ & ~*cp++); 420} 421 422/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 423 424void 425sbitmap_not (sbitmap dst, const_sbitmap src) 426{ 427 unsigned int i, n = dst->size; 428 sbitmap_ptr dstp = dst->elms; 429 const_sbitmap_ptr srcp = src->elms; 430 unsigned int last_bit; 431 432 gcc_assert (!dst->popcount); 433 434 for (i = 0; i < n; i++) 435 *dstp++ = ~*srcp++; 436 437 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */ 438 last_bit = src->n_bits % SBITMAP_ELT_BITS; 439 if (last_bit) 440 dst->elms[n-1] = dst->elms[n-1] 441 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 442} 443 444/* Set the bits in DST to be the difference between the bits 445 in A and the bits in B. i.e. dst = a & (~b). */ 446 447void 448sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b) 449{ 450 unsigned int i, dst_size = dst->size; 451 unsigned int min_size = dst->size; 452 sbitmap_ptr dstp = dst->elms; 453 const_sbitmap_ptr ap = a->elms; 454 const_sbitmap_ptr bp = b->elms; 455 456 gcc_assert (!dst->popcount); 457 458 /* A should be at least as large as DEST, to have a defined source. */ 459 gcc_assert (a->size >= dst_size); 460 /* If minuend is smaller, we simply pretend it to be zero bits, i.e. 461 only copy the subtrahend into dest. */ 462 if (b->size < min_size) 463 min_size = b->size; 464 for (i = 0; i < min_size; i++) 465 *dstp++ = *ap++ & (~*bp++); 466 /* Now fill the rest of dest from A, if B was too short. 467 This makes sense only when destination and A differ. */ 468 if (dst != a && i != dst_size) 469 for (; i < dst_size; i++) 470 *dstp++ = *ap++; 471} 472 473/* Return true if there are any bits set in A are also set in B. 474 Return false otherwise. */ 475 476bool 477sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b) 478{ 479 const_sbitmap_ptr ap = a->elms; 480 const_sbitmap_ptr bp = b->elms; 481 unsigned int i, n; 482 483 n = MIN (a->size, b->size); 484 for (i = 0; i < n; i++) 485 if ((*ap++ & *bp++) != 0) 486 return true; 487 488 return false; 489} 490 491/* Set DST to be (A and B). 492 Return nonzero if any change is made. */ 493 494bool 495sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b) 496{ 497 unsigned int i, n = dst->size; 498 sbitmap_ptr dstp = dst->elms; 499 const_sbitmap_ptr ap = a->elms; 500 const_sbitmap_ptr bp = b->elms; 501 SBITMAP_ELT_TYPE changed = 0; 502 503 gcc_assert (!dst->popcount); 504 505 for (i = 0; i < n; i++) 506 { 507 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 508 changed |= *dstp ^ tmp; 509 *dstp++ = tmp; 510 } 511 512 return changed != 0; 513} 514 515void 516sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b) 517{ 518 unsigned int i, n = dst->size; 519 sbitmap_ptr dstp = dst->elms; 520 const_sbitmap_ptr ap = a->elms; 521 const_sbitmap_ptr bp = b->elms; 522 bool has_popcount = dst->popcount != NULL; 523 unsigned char *popcountp = dst->popcount; 524 525 for (i = 0; i < n; i++) 526 { 527 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 528 if (has_popcount) 529 { 530 bool wordchanged = (*dstp ^ tmp) != 0; 531 if (wordchanged) 532 *popcountp = do_popcount (tmp); 533 popcountp++; 534 } 535 *dstp++ = tmp; 536 } 537#ifdef BITMAP_DEBUGGING 538 if (has_popcount) 539 sbitmap_verify_popcount (dst); 540#endif 541} 542 543/* Set DST to be (A xor B)). 544 Return nonzero if any change is made. */ 545 546bool 547sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b) 548{ 549 unsigned int i, n = dst->size; 550 sbitmap_ptr dstp = dst->elms; 551 const_sbitmap_ptr ap = a->elms; 552 const_sbitmap_ptr bp = b->elms; 553 SBITMAP_ELT_TYPE changed = 0; 554 555 gcc_assert (!dst->popcount); 556 557 for (i = 0; i < n; i++) 558 { 559 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 560 changed |= *dstp ^ tmp; 561 *dstp++ = tmp; 562 } 563 564 return changed != 0; 565} 566 567void 568sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b) 569{ 570 unsigned int i, n = dst->size; 571 sbitmap_ptr dstp = dst->elms; 572 const_sbitmap_ptr ap = a->elms; 573 const_sbitmap_ptr bp = b->elms; 574 bool has_popcount = dst->popcount != NULL; 575 unsigned char *popcountp = dst->popcount; 576 577 for (i = 0; i < n; i++) 578 { 579 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 580 if (has_popcount) 581 { 582 bool wordchanged = (*dstp ^ tmp) != 0; 583 if (wordchanged) 584 *popcountp = do_popcount (tmp); 585 popcountp++; 586 } 587 *dstp++ = tmp; 588 } 589#ifdef BITMAP_DEBUGGING 590 if (has_popcount) 591 sbitmap_verify_popcount (dst); 592#endif 593} 594 595/* Set DST to be (A or B)). 596 Return nonzero if any change is made. */ 597 598bool 599sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b) 600{ 601 unsigned int i, n = dst->size; 602 sbitmap_ptr dstp = dst->elms; 603 const_sbitmap_ptr ap = a->elms; 604 const_sbitmap_ptr bp = b->elms; 605 SBITMAP_ELT_TYPE changed = 0; 606 607 gcc_assert (!dst->popcount); 608 609 for (i = 0; i < n; i++) 610 { 611 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 612 changed |= *dstp ^ tmp; 613 *dstp++ = tmp; 614 } 615 616 return changed != 0; 617} 618 619void 620sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b) 621{ 622 unsigned int i, n = dst->size; 623 sbitmap_ptr dstp = dst->elms; 624 const_sbitmap_ptr ap = a->elms; 625 const_sbitmap_ptr bp = b->elms; 626 bool has_popcount = dst->popcount != NULL; 627 unsigned char *popcountp = dst->popcount; 628 629 for (i = 0; i < n; i++) 630 { 631 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 632 if (has_popcount) 633 { 634 bool wordchanged = (*dstp ^ tmp) != 0; 635 if (wordchanged) 636 *popcountp = do_popcount (tmp); 637 popcountp++; 638 } 639 *dstp++ = tmp; 640 } 641#ifdef BITMAP_DEBUGGING 642 if (has_popcount) 643 sbitmap_verify_popcount (dst); 644#endif 645} 646 647/* Return nonzero if A is a subset of B. */ 648 649bool 650sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b) 651{ 652 unsigned int i, n = a->size; 653 const_sbitmap_ptr ap, bp; 654 655 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) 656 if ((*ap | *bp) != *bp) 657 return false; 658 659 return true; 660} 661 662/* Set DST to be (A or (B and C)). 663 Return nonzero if any change is made. */ 664 665bool 666sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 667{ 668 unsigned int i, n = dst->size; 669 sbitmap_ptr dstp = dst->elms; 670 const_sbitmap_ptr ap = a->elms; 671 const_sbitmap_ptr bp = b->elms; 672 const_sbitmap_ptr cp = c->elms; 673 SBITMAP_ELT_TYPE changed = 0; 674 675 gcc_assert (!dst->popcount); 676 677 for (i = 0; i < n; i++) 678 { 679 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 680 changed |= *dstp ^ tmp; 681 *dstp++ = tmp; 682 } 683 684 return changed != 0; 685} 686 687void 688sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 689{ 690 unsigned int i, n = dst->size; 691 sbitmap_ptr dstp = dst->elms; 692 const_sbitmap_ptr ap = a->elms; 693 const_sbitmap_ptr bp = b->elms; 694 const_sbitmap_ptr cp = c->elms; 695 696 gcc_assert (!dst->popcount); 697 698 for (i = 0; i < n; i++) 699 *dstp++ = *ap++ | (*bp++ & *cp++); 700} 701 702/* Set DST to be (A and (B or C)). 703 Return nonzero if any change is made. */ 704 705bool 706sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 707{ 708 unsigned int i, n = dst->size; 709 sbitmap_ptr dstp = dst->elms; 710 const_sbitmap_ptr ap = a->elms; 711 const_sbitmap_ptr bp = b->elms; 712 const_sbitmap_ptr cp = c->elms; 713 SBITMAP_ELT_TYPE changed = 0; 714 715 gcc_assert (!dst->popcount); 716 717 for (i = 0; i < n; i++) 718 { 719 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 720 changed |= *dstp ^ tmp; 721 *dstp++ = tmp; 722 } 723 724 return changed != 0; 725} 726 727void 728sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 729{ 730 unsigned int i, n = dst->size; 731 sbitmap_ptr dstp = dst->elms; 732 const_sbitmap_ptr ap = a->elms; 733 const_sbitmap_ptr bp = b->elms; 734 const_sbitmap_ptr cp = c->elms; 735 736 for (i = 0; i < n; i++) 737 *dstp++ = *ap++ & (*bp++ | *cp++); 738} 739 740#ifdef IN_GCC 741/* Set the bitmap DST to the intersection of SRC of successors of 742 block number BB, using the new flow graph structures. */ 743 744void 745sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) 746{ 747 basic_block b = BASIC_BLOCK (bb); 748 unsigned int set_size = dst->size; 749 edge e; 750 unsigned ix; 751 752 gcc_assert (!dst->popcount); 753 754 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) 755 { 756 e = EDGE_SUCC (b, ix); 757 if (e->dest == EXIT_BLOCK_PTR) 758 continue; 759 760 sbitmap_copy (dst, src[e->dest->index]); 761 break; 762 } 763 764 if (e == 0) 765 sbitmap_ones (dst); 766 else 767 for (++ix; ix < EDGE_COUNT (b->succs); ix++) 768 { 769 unsigned int i; 770 sbitmap_ptr p, r; 771 772 e = EDGE_SUCC (b, ix); 773 if (e->dest == EXIT_BLOCK_PTR) 774 continue; 775 776 p = src[e->dest->index]->elms; 777 r = dst->elms; 778 for (i = 0; i < set_size; i++) 779 *r++ &= *p++; 780 } 781} 782 783/* Set the bitmap DST to the intersection of SRC of predecessors of 784 block number BB, using the new flow graph structures. */ 785 786void 787sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) 788{ 789 basic_block b = BASIC_BLOCK (bb); 790 unsigned int set_size = dst->size; 791 edge e; 792 unsigned ix; 793 794 gcc_assert (!dst->popcount); 795 796 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) 797 { 798 e = EDGE_PRED (b, ix); 799 if (e->src == ENTRY_BLOCK_PTR) 800 continue; 801 802 sbitmap_copy (dst, src[e->src->index]); 803 break; 804 } 805 806 if (e == 0) 807 sbitmap_ones (dst); 808 else 809 for (++ix; ix < EDGE_COUNT (b->preds); ix++) 810 { 811 unsigned int i; 812 sbitmap_ptr p, r; 813 814 e = EDGE_PRED (b, ix); 815 if (e->src == ENTRY_BLOCK_PTR) 816 continue; 817 818 p = src[e->src->index]->elms; 819 r = dst->elms; 820 for (i = 0; i < set_size; i++) 821 *r++ &= *p++; 822 } 823} 824 825/* Set the bitmap DST to the union of SRC of successors of 826 block number BB, using the new flow graph structures. */ 827 828void 829sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) 830{ 831 basic_block b = BASIC_BLOCK (bb); 832 unsigned int set_size = dst->size; 833 edge e; 834 unsigned ix; 835 836 gcc_assert (!dst->popcount); 837 838 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) 839 { 840 e = EDGE_SUCC (b, ix); 841 if (e->dest == EXIT_BLOCK_PTR) 842 continue; 843 844 sbitmap_copy (dst, src[e->dest->index]); 845 break; 846 } 847 848 if (ix == EDGE_COUNT (b->succs)) 849 sbitmap_zero (dst); 850 else 851 for (ix++; ix < EDGE_COUNT (b->succs); ix++) 852 { 853 unsigned int i; 854 sbitmap_ptr p, r; 855 856 e = EDGE_SUCC (b, ix); 857 if (e->dest == EXIT_BLOCK_PTR) 858 continue; 859 860 p = src[e->dest->index]->elms; 861 r = dst->elms; 862 for (i = 0; i < set_size; i++) 863 *r++ |= *p++; 864 } 865} 866 867/* Set the bitmap DST to the union of SRC of predecessors of 868 block number BB, using the new flow graph structures. */ 869 870void 871sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) 872{ 873 basic_block b = BASIC_BLOCK (bb); 874 unsigned int set_size = dst->size; 875 edge e; 876 unsigned ix; 877 878 gcc_assert (!dst->popcount); 879 880 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) 881 { 882 e = EDGE_PRED (b, ix); 883 if (e->src== ENTRY_BLOCK_PTR) 884 continue; 885 886 sbitmap_copy (dst, src[e->src->index]); 887 break; 888 } 889 890 if (ix == EDGE_COUNT (b->preds)) 891 sbitmap_zero (dst); 892 else 893 for (ix++; ix < EDGE_COUNT (b->preds); ix++) 894 { 895 unsigned int i; 896 sbitmap_ptr p, r; 897 898 e = EDGE_PRED (b, ix); 899 if (e->src == ENTRY_BLOCK_PTR) 900 continue; 901 902 p = src[e->src->index]->elms; 903 r = dst->elms; 904 for (i = 0; i < set_size; i++) 905 *r++ |= *p++; 906 } 907} 908#endif 909 910/* Return number of first bit set in the bitmap, -1 if none. */ 911 912int 913sbitmap_first_set_bit (const_sbitmap bmap) 914{ 915 unsigned int n = 0; 916 sbitmap_iterator sbi; 917 918 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi) 919 return n; 920 return -1; 921} 922 923/* Return number of last bit set in the bitmap, -1 if none. */ 924 925int 926sbitmap_last_set_bit (const_sbitmap bmap) 927{ 928 int i; 929 const SBITMAP_ELT_TYPE *const ptr = bmap->elms; 930 931 for (i = bmap->size - 1; i >= 0; i--) 932 { 933 const SBITMAP_ELT_TYPE word = ptr[i]; 934 935 if (word != 0) 936 { 937 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 938 SBITMAP_ELT_TYPE mask 939 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 940 941 while (1) 942 { 943 if ((word & mask) != 0) 944 return index; 945 946 mask >>= 1; 947 index--; 948 } 949 } 950 } 951 952 return -1; 953} 954 955void 956dump_sbitmap (FILE *file, const_sbitmap bmap) 957{ 958 unsigned int i, n, j; 959 unsigned int set_size = bmap->size; 960 unsigned int total_bits = bmap->n_bits; 961 962 fprintf (file, " "); 963 for (i = n = 0; i < set_size && n < total_bits; i++) 964 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 965 { 966 if (n != 0 && n % 10 == 0) 967 fprintf (file, " "); 968 969 fprintf (file, "%d", 970 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 971 } 972 973 fprintf (file, "\n"); 974} 975 976void 977dump_sbitmap_file (FILE *file, const_sbitmap bmap) 978{ 979 unsigned int i, pos; 980 981 fprintf (file, "n_bits = %d, set = {", bmap->n_bits); 982 983 for (pos = 30, i = 0; i < bmap->n_bits; i++) 984 if (TEST_BIT (bmap, i)) 985 { 986 if (pos > 70) 987 { 988 fprintf (file, "\n "); 989 pos = 0; 990 } 991 992 fprintf (file, "%d ", i); 993 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); 994 } 995 996 fprintf (file, "}\n"); 997} 998 999void 1000debug_sbitmap (const_sbitmap bmap) 1001{ 1002 dump_sbitmap_file (stderr, bmap); 1003} 1004 1005void 1006dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, 1007 sbitmap *bmaps, int n_maps) 1008{ 1009 int bb; 1010 1011 fprintf (file, "%s\n", title); 1012 for (bb = 0; bb < n_maps; bb++) 1013 { 1014 fprintf (file, "%s %d\n", subtitle, bb); 1015 dump_sbitmap (file, bmaps[bb]); 1016 } 1017 1018 fprintf (file, "\n"); 1019} 1020 1021#if GCC_VERSION < 3400 1022/* Table of number of set bits in a character, indexed by value of char. */ 1023static const unsigned char popcount_table[] = 1024{ 1025 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 1026 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1027 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1028 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1029 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 1030 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1031 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 1032 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 1033}; 1034 1035/* Count the bits in an SBITMAP element A. */ 1036 1037static unsigned long 1038sbitmap_elt_popcount (SBITMAP_ELT_TYPE a) 1039{ 1040 unsigned long ret = 0; 1041 unsigned i; 1042 1043 if (a == 0) 1044 return 0; 1045 1046 /* Just do this the table way for now */ 1047 for (i = 0; i < SBITMAP_ELT_BITS; i += 8) 1048 ret += popcount_table[(a >> i) & 0xff]; 1049 return ret; 1050} 1051#endif 1052 1053/* Count the number of bits in SBITMAP a, up to bit MAXBIT. */ 1054 1055unsigned long 1056sbitmap_popcount (const_sbitmap a, unsigned long maxbit) 1057{ 1058 unsigned long count = 0; 1059 unsigned ix; 1060 unsigned int lastword; 1061 1062 if (maxbit == 0) 1063 return 0; 1064 1065 if (maxbit >= a->n_bits) 1066 maxbit = a->n_bits; 1067 1068 /* Count the bits in the full word. */ 1069 lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1); 1070 for (ix = 0; ix < lastword; ix++) 1071 { 1072 if (a->popcount) 1073 { 1074 count += a->popcount[ix]; 1075#ifdef BITMAP_DEBUGGING 1076 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix])); 1077#endif 1078 } 1079 else 1080 count += do_popcount (a->elms[ix]); 1081 } 1082 1083 /* Count the remaining bits. */ 1084 if (lastword < a->size) 1085 { 1086 unsigned int bitindex; 1087 SBITMAP_ELT_TYPE theword = a->elms[lastword]; 1088 1089 bitindex = maxbit % SBITMAP_ELT_BITS; 1090 if (bitindex != 0) 1091 { 1092 theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex); 1093 count += do_popcount (theword); 1094 } 1095 } 1096 return count; 1097} 1098 1099