sbitmap.c revision 132718
1/* Simple bitmaps. 2 Copyright (C) 1999, 2000, 2002, 2003 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 2, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to the Free 18Software Foundation, 59 Temple Place - Suite 330, Boston, MA 1902111-1307, USA. */ 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 "basic-block.h" 29 30/* Bitmap manipulation routines. */ 31 32/* Allocate a simple bitmap of N_ELMS bits. */ 33 34sbitmap 35sbitmap_alloc (unsigned int n_elms) 36{ 37 unsigned int bytes, size, amt; 38 sbitmap bmap; 39 40 size = SBITMAP_SET_SIZE (n_elms); 41 bytes = size * sizeof (SBITMAP_ELT_TYPE); 42 amt = (sizeof (struct simple_bitmap_def) 43 + bytes - sizeof (SBITMAP_ELT_TYPE)); 44 bmap = xmalloc (amt); 45 bmap->n_bits = n_elms; 46 bmap->size = size; 47 bmap->bytes = bytes; 48 return bmap; 49} 50 51/* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the 52 size of BMAP, clear the new bits to zero if the DEF argument 53 is zero, and set them to one otherwise. */ 54 55sbitmap 56sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) 57{ 58 unsigned int bytes, size, amt; 59 unsigned int last_bit; 60 61 size = SBITMAP_SET_SIZE (n_elms); 62 bytes = size * sizeof (SBITMAP_ELT_TYPE); 63 if (bytes > bmap->bytes) 64 { 65 amt = (sizeof (struct simple_bitmap_def) 66 + bytes - sizeof (SBITMAP_ELT_TYPE)); 67 bmap = xrealloc (bmap, amt); 68 } 69 70 if (n_elms > bmap->n_bits) 71 { 72 if (def) 73 { 74 memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes); 75 76 /* Set the new bits if the original last element. */ 77 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 78 if (last_bit) 79 bmap->elms[bmap->size - 1] 80 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 81 82 /* Clear the unused bit in the new last element. */ 83 last_bit = n_elms % SBITMAP_ELT_BITS; 84 if (last_bit) 85 bmap->elms[size - 1] 86 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 87 } 88 else 89 memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes); 90 } 91 else if (n_elms < bmap->n_bits) 92 { 93 /* Clear the surplus bits in the last word. */ 94 last_bit = n_elms % SBITMAP_ELT_BITS; 95 if (last_bit) 96 bmap->elms[size - 1] 97 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 98 } 99 100 bmap->n_bits = n_elms; 101 bmap->size = size; 102 bmap->bytes = bytes; 103 return bmap; 104} 105 106/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 107 108sbitmap * 109sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) 110{ 111 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 112 sbitmap *bitmap_vector; 113 114 size = SBITMAP_SET_SIZE (n_elms); 115 bytes = size * sizeof (SBITMAP_ELT_TYPE); 116 elm_bytes = (sizeof (struct simple_bitmap_def) 117 + bytes - sizeof (SBITMAP_ELT_TYPE)); 118 vector_bytes = n_vecs * sizeof (sbitmap *); 119 120 /* Round up `vector_bytes' to account for the alignment requirements 121 of an sbitmap. One could allocate the vector-table and set of sbitmaps 122 separately, but that requires maintaining two pointers or creating 123 a cover struct to hold both pointers (so our result is still just 124 one pointer). Neither is a bad idea, but this is simpler for now. */ 125 { 126 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 127 struct { char x; SBITMAP_ELT_TYPE y; } align; 128 int alignment = (char *) & align.y - & align.x; 129 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 130 } 131 132 amt = vector_bytes + (n_vecs * elm_bytes); 133 bitmap_vector = xmalloc (amt); 134 135 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 136 { 137 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 138 139 bitmap_vector[i] = b; 140 b->n_bits = n_elms; 141 b->size = size; 142 b->bytes = bytes; 143 } 144 145 return bitmap_vector; 146} 147 148/* Copy sbitmap SRC to DST. */ 149 150void 151sbitmap_copy (sbitmap dst, sbitmap src) 152{ 153 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 154} 155 156/* Determine if a == b. */ 157int 158sbitmap_equal (sbitmap a, sbitmap b) 159{ 160 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 161} 162 163/* Zero all elements in a bitmap. */ 164 165void 166sbitmap_zero (sbitmap bmap) 167{ 168 memset (bmap->elms, 0, bmap->bytes); 169} 170 171/* Set all elements in a bitmap to ones. */ 172 173void 174sbitmap_ones (sbitmap bmap) 175{ 176 unsigned int last_bit; 177 178 memset (bmap->elms, -1, bmap->bytes); 179 180 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 181 if (last_bit) 182 bmap->elms[bmap->size - 1] 183 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 184} 185 186/* Zero a vector of N_VECS bitmaps. */ 187 188void 189sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs) 190{ 191 unsigned int i; 192 193 for (i = 0; i < n_vecs; i++) 194 sbitmap_zero (bmap[i]); 195} 196 197/* Set a vector of N_VECS bitmaps to ones. */ 198 199void 200sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) 201{ 202 unsigned int i; 203 204 for (i = 0; i < n_vecs; i++) 205 sbitmap_ones (bmap[i]); 206} 207 208/* Set DST to be A union (B - C). 209 DST = A | (B & ~C). 210 Returns true if any change is made. */ 211 212bool 213sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 214{ 215 unsigned int i, n = dst->size; 216 sbitmap_ptr dstp = dst->elms; 217 sbitmap_ptr ap = a->elms; 218 sbitmap_ptr bp = b->elms; 219 sbitmap_ptr cp = c->elms; 220 SBITMAP_ELT_TYPE changed = 0; 221 222 for (i = 0; i < n; i++) 223 { 224 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 225 changed |= *dstp ^ tmp; 226 *dstp++ = tmp; 227 } 228 229 return changed != 0; 230} 231 232void 233sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 234{ 235 unsigned int i, n = dst->size; 236 sbitmap_ptr dstp = dst->elms; 237 sbitmap_ptr ap = a->elms; 238 sbitmap_ptr bp = b->elms; 239 sbitmap_ptr cp = c->elms; 240 241 for (i = 0; i < n; i++) 242 *dstp++ = *ap++ | (*bp++ & ~*cp++); 243} 244 245/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 246 247void 248sbitmap_not (sbitmap dst, sbitmap src) 249{ 250 unsigned int i, n = dst->size; 251 sbitmap_ptr dstp = dst->elms; 252 sbitmap_ptr srcp = src->elms; 253 unsigned int last_bit; 254 255 for (i = 0; i < n; i++) 256 *dstp++ = ~*srcp++; 257 258 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */ 259 last_bit = src->n_bits % SBITMAP_ELT_BITS; 260 if (last_bit) 261 dst->elms[n-1] = dst->elms[n-1] 262 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 263} 264 265/* Set the bits in DST to be the difference between the bits 266 in A and the bits in B. i.e. dst = a & (~b). */ 267 268void 269sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b) 270{ 271 unsigned int i, dst_size = dst->size; 272 unsigned int min_size = dst->size; 273 sbitmap_ptr dstp = dst->elms; 274 sbitmap_ptr ap = a->elms; 275 sbitmap_ptr bp = b->elms; 276 277 /* A should be at least as large as DEST, to have a defined source. */ 278 if (a->size < dst_size) 279 abort (); 280 /* If minuend is smaller, we simply pretend it to be zero bits, i.e. 281 only copy the subtrahend into dest. */ 282 if (b->size < min_size) 283 min_size = b->size; 284 for (i = 0; i < min_size; i++) 285 *dstp++ = *ap++ & (~*bp++); 286 /* Now fill the rest of dest from A, if B was too short. 287 This makes sense only when destination and A differ. */ 288 if (dst != a && i != dst_size) 289 for (; i < dst_size; i++) 290 *dstp++ = *ap++; 291} 292 293/* Set DST to be (A and B). 294 Return nonzero if any change is made. */ 295 296bool 297sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b) 298{ 299 unsigned int i, n = dst->size; 300 sbitmap_ptr dstp = dst->elms; 301 sbitmap_ptr ap = a->elms; 302 sbitmap_ptr bp = b->elms; 303 SBITMAP_ELT_TYPE changed = 0; 304 305 for (i = 0; i < n; i++) 306 { 307 SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 308 changed |= *dstp ^ tmp; 309 *dstp++ = tmp; 310 } 311 312 return changed != 0; 313} 314 315void 316sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b) 317{ 318 unsigned int i, n = dst->size; 319 sbitmap_ptr dstp = dst->elms; 320 sbitmap_ptr ap = a->elms; 321 sbitmap_ptr bp = b->elms; 322 323 for (i = 0; i < n; i++) 324 *dstp++ = *ap++ & *bp++; 325} 326 327/* Set DST to be (A xor B)). 328 Return nonzero if any change is made. */ 329 330bool 331sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b) 332{ 333 unsigned int i, n = dst->size; 334 sbitmap_ptr dstp = dst->elms; 335 sbitmap_ptr ap = a->elms; 336 sbitmap_ptr bp = b->elms; 337 SBITMAP_ELT_TYPE changed = 0; 338 339 for (i = 0; i < n; i++) 340 { 341 SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 342 changed |= *dstp ^ tmp; 343 *dstp++ = tmp; 344 } 345 346 return changed != 0; 347} 348 349void 350sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b) 351{ 352 unsigned int i, n = dst->size; 353 sbitmap_ptr dstp = dst->elms; 354 sbitmap_ptr ap = a->elms; 355 sbitmap_ptr bp = b->elms; 356 357 for (i = 0; i < n; i++) 358 *dstp++ = *ap++ ^ *bp++; 359} 360 361/* Set DST to be (A or B)). 362 Return nonzero if any change is made. */ 363 364bool 365sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b) 366{ 367 unsigned int i, n = dst->size; 368 sbitmap_ptr dstp = dst->elms; 369 sbitmap_ptr ap = a->elms; 370 sbitmap_ptr bp = b->elms; 371 SBITMAP_ELT_TYPE changed = 0; 372 373 for (i = 0; i < n; i++) 374 { 375 SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 376 changed |= *dstp ^ tmp; 377 *dstp++ = tmp; 378 } 379 380 return changed != 0; 381} 382 383void 384sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b) 385{ 386 unsigned int i, n = dst->size; 387 sbitmap_ptr dstp = dst->elms; 388 sbitmap_ptr ap = a->elms; 389 sbitmap_ptr bp = b->elms; 390 391 for (i = 0; i < n; i++) 392 *dstp++ = *ap++ | *bp++; 393} 394 395/* Return nonzero if A is a subset of B. */ 396 397bool 398sbitmap_a_subset_b_p (sbitmap a, sbitmap b) 399{ 400 unsigned int i, n = a->size; 401 sbitmap_ptr ap, bp; 402 403 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) 404 if ((*ap | *bp) != *bp) 405 return false; 406 407 return true; 408} 409 410/* Set DST to be (A or (B and C)). 411 Return nonzero if any change is made. */ 412 413bool 414sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 415{ 416 unsigned int i, n = dst->size; 417 sbitmap_ptr dstp = dst->elms; 418 sbitmap_ptr ap = a->elms; 419 sbitmap_ptr bp = b->elms; 420 sbitmap_ptr cp = c->elms; 421 SBITMAP_ELT_TYPE changed = 0; 422 423 for (i = 0; i < n; i++) 424 { 425 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 426 changed |= *dstp ^ tmp; 427 *dstp++ = tmp; 428 } 429 430 return changed != 0; 431} 432 433void 434sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 435{ 436 unsigned int i, n = dst->size; 437 sbitmap_ptr dstp = dst->elms; 438 sbitmap_ptr ap = a->elms; 439 sbitmap_ptr bp = b->elms; 440 sbitmap_ptr cp = c->elms; 441 442 for (i = 0; i < n; i++) 443 *dstp++ = *ap++ | (*bp++ & *cp++); 444} 445 446/* Set DST to be (A and (B or C)). 447 Return nonzero if any change is made. */ 448 449bool 450sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 451{ 452 unsigned int i, n = dst->size; 453 sbitmap_ptr dstp = dst->elms; 454 sbitmap_ptr ap = a->elms; 455 sbitmap_ptr bp = b->elms; 456 sbitmap_ptr cp = c->elms; 457 SBITMAP_ELT_TYPE changed = 0; 458 459 for (i = 0; i < n; i++) 460 { 461 SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 462 changed |= *dstp ^ tmp; 463 *dstp++ = tmp; 464 } 465 466 return changed != 0; 467} 468 469void 470sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c) 471{ 472 unsigned int i, n = dst->size; 473 sbitmap_ptr dstp = dst->elms; 474 sbitmap_ptr ap = a->elms; 475 sbitmap_ptr bp = b->elms; 476 sbitmap_ptr cp = c->elms; 477 478 for (i = 0; i < n; i++) 479 *dstp++ = *ap++ & (*bp++ | *cp++); 480} 481 482#ifdef IN_GCC 483/* Set the bitmap DST to the intersection of SRC of successors of 484 block number BB, using the new flow graph structures. */ 485 486void 487sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) 488{ 489 basic_block b = BASIC_BLOCK (bb); 490 unsigned int set_size = dst->size; 491 edge e; 492 493 for (e = b->succ; e != 0; e = e->succ_next) 494 { 495 if (e->dest == EXIT_BLOCK_PTR) 496 continue; 497 498 sbitmap_copy (dst, src[e->dest->index]); 499 break; 500 } 501 502 if (e == 0) 503 sbitmap_ones (dst); 504 else 505 for (e = e->succ_next; e != 0; e = e->succ_next) 506 { 507 unsigned int i; 508 sbitmap_ptr p, r; 509 510 if (e->dest == EXIT_BLOCK_PTR) 511 continue; 512 513 p = src[e->dest->index]->elms; 514 r = dst->elms; 515 for (i = 0; i < set_size; i++) 516 *r++ &= *p++; 517 } 518} 519 520/* Set the bitmap DST to the intersection of SRC of predecessors of 521 block number BB, using the new flow graph structures. */ 522 523void 524sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb) 525{ 526 basic_block b = BASIC_BLOCK (bb); 527 unsigned int set_size = dst->size; 528 edge e; 529 530 for (e = b->pred; e != 0; e = e->pred_next) 531 { 532 if (e->src == ENTRY_BLOCK_PTR) 533 continue; 534 535 sbitmap_copy (dst, src[e->src->index]); 536 break; 537 } 538 539 if (e == 0) 540 sbitmap_ones (dst); 541 else 542 for (e = e->pred_next; e != 0; e = e->pred_next) 543 { 544 unsigned int i; 545 sbitmap_ptr p, r; 546 547 if (e->src == ENTRY_BLOCK_PTR) 548 continue; 549 550 p = src[e->src->index]->elms; 551 r = dst->elms; 552 for (i = 0; i < set_size; i++) 553 *r++ &= *p++; 554 } 555} 556 557/* Set the bitmap DST to the union of SRC of successors of 558 block number BB, using the new flow graph structures. */ 559 560void 561sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb) 562{ 563 basic_block b = BASIC_BLOCK (bb); 564 unsigned int set_size = dst->size; 565 edge e; 566 567 for (e = b->succ; e != 0; e = e->succ_next) 568 { 569 if (e->dest == EXIT_BLOCK_PTR) 570 continue; 571 572 sbitmap_copy (dst, src[e->dest->index]); 573 break; 574 } 575 576 if (e == 0) 577 sbitmap_zero (dst); 578 else 579 for (e = e->succ_next; e != 0; e = e->succ_next) 580 { 581 unsigned int i; 582 sbitmap_ptr p, r; 583 584 if (e->dest == EXIT_BLOCK_PTR) 585 continue; 586 587 p = src[e->dest->index]->elms; 588 r = dst->elms; 589 for (i = 0; i < set_size; i++) 590 *r++ |= *p++; 591 } 592} 593 594/* Set the bitmap DST to the union of SRC of predecessors of 595 block number BB, using the new flow graph structures. */ 596 597void 598sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb) 599{ 600 basic_block b = BASIC_BLOCK (bb); 601 unsigned int set_size = dst->size; 602 edge e; 603 604 for (e = b->pred; e != 0; e = e->pred_next) 605 { 606 if (e->src== ENTRY_BLOCK_PTR) 607 continue; 608 609 sbitmap_copy (dst, src[e->src->index]); 610 break; 611 } 612 613 if (e == 0) 614 sbitmap_zero (dst); 615 else 616 for (e = e->pred_next; e != 0; e = e->pred_next) 617 { 618 unsigned int i; 619 sbitmap_ptr p, r; 620 621 if (e->src == ENTRY_BLOCK_PTR) 622 continue; 623 624 p = src[e->src->index]->elms; 625 r = dst->elms; 626 for (i = 0; i < set_size; i++) 627 *r++ |= *p++; 628 } 629} 630#endif 631 632/* Return number of first bit set in the bitmap, -1 if none. */ 633 634int 635sbitmap_first_set_bit (sbitmap bmap) 636{ 637 unsigned int n; 638 639 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; }); 640 return -1; 641} 642 643/* Return number of last bit set in the bitmap, -1 if none. */ 644 645int 646sbitmap_last_set_bit (sbitmap bmap) 647{ 648 int i; 649 SBITMAP_ELT_TYPE *ptr = bmap->elms; 650 651 for (i = bmap->size - 1; i >= 0; i--) 652 { 653 SBITMAP_ELT_TYPE word = ptr[i]; 654 655 if (word != 0) 656 { 657 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 658 SBITMAP_ELT_TYPE mask 659 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 660 661 while (1) 662 { 663 if ((word & mask) != 0) 664 return index; 665 666 mask >>= 1; 667 index--; 668 } 669 } 670 } 671 672 return -1; 673} 674 675void 676dump_sbitmap (FILE *file, sbitmap bmap) 677{ 678 unsigned int i, n, j; 679 unsigned int set_size = bmap->size; 680 unsigned int total_bits = bmap->n_bits; 681 682 fprintf (file, " "); 683 for (i = n = 0; i < set_size && n < total_bits; i++) 684 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 685 { 686 if (n != 0 && n % 10 == 0) 687 fprintf (file, " "); 688 689 fprintf (file, "%d", 690 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 691 } 692 693 fprintf (file, "\n"); 694} 695 696void 697dump_sbitmap_file (FILE *file, sbitmap bmap) 698{ 699 unsigned int i, pos; 700 701 fprintf (file, "n_bits = %d, set = {", bmap->n_bits); 702 703 for (pos = 30, i = 0; i < bmap->n_bits; i++) 704 if (TEST_BIT (bmap, i)) 705 { 706 if (pos > 70) 707 { 708 fprintf (file, "\n "); 709 pos = 0; 710 } 711 712 fprintf (file, "%d ", i); 713 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); 714 } 715 716 fprintf (file, "}\n"); 717} 718 719void 720debug_sbitmap (sbitmap bmap) 721{ 722 dump_sbitmap_file (stderr, bmap); 723} 724 725void 726dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle, 727 sbitmap *bmaps, int n_maps) 728{ 729 int bb; 730 731 fprintf (file, "%s\n", title); 732 for (bb = 0; bb < n_maps; bb++) 733 { 734 fprintf (file, "%s %d\n", subtitle, bb); 735 dump_sbitmap (file, bmaps[bb]); 736 } 737 738 fprintf (file, "\n"); 739} 740