sbitmap.c revision 90075
1/* Simple bitmaps. 2 Copyright (C) 1999, 2000 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 "rtl.h" 24#include "flags.h" 25#include "hard-reg-set.h" 26#include "basic-block.h" 27 28/* Bitmap manipulation routines. */ 29 30/* Allocate a simple bitmap of N_ELMS bits. */ 31 32sbitmap 33sbitmap_alloc (n_elms) 34 unsigned int n_elms; 35{ 36 unsigned int bytes, size, amt; 37 sbitmap bmap; 38 39 size = SBITMAP_SET_SIZE (n_elms); 40 bytes = size * sizeof (SBITMAP_ELT_TYPE); 41 amt = (sizeof (struct simple_bitmap_def) 42 + bytes - sizeof (SBITMAP_ELT_TYPE)); 43 bmap = (sbitmap) xmalloc (amt); 44 bmap->n_bits = n_elms; 45 bmap->size = size; 46 bmap->bytes = bytes; 47 return bmap; 48} 49 50/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 51 52sbitmap * 53sbitmap_vector_alloc (n_vecs, n_elms) 54 unsigned int n_vecs, n_elms; 55{ 56 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 57 sbitmap *bitmap_vector; 58 59 size = SBITMAP_SET_SIZE (n_elms); 60 bytes = size * sizeof (SBITMAP_ELT_TYPE); 61 elm_bytes = (sizeof (struct simple_bitmap_def) 62 + bytes - sizeof (SBITMAP_ELT_TYPE)); 63 vector_bytes = n_vecs * sizeof (sbitmap *); 64 65 /* Round up `vector_bytes' to account for the alignment requirements 66 of an sbitmap. One could allocate the vector-table and set of sbitmaps 67 separately, but that requires maintaining two pointers or creating 68 a cover struct to hold both pointers (so our result is still just 69 one pointer). Neither is a bad idea, but this is simpler for now. */ 70 { 71 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 72 struct { char x; SBITMAP_ELT_TYPE y; } align; 73 int alignment = (char *) & align.y - & align.x; 74 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 75 } 76 77 amt = vector_bytes + (n_vecs * elm_bytes); 78 bitmap_vector = (sbitmap *) xmalloc (amt); 79 80 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 81 { 82 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 83 84 bitmap_vector[i] = b; 85 b->n_bits = n_elms; 86 b->size = size; 87 b->bytes = bytes; 88 } 89 90 return bitmap_vector; 91} 92 93/* Copy sbitmap SRC to DST. */ 94 95void 96sbitmap_copy (dst, src) 97 sbitmap dst, src; 98{ 99 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 100} 101 102/* Determine if a == b. */ 103int 104sbitmap_equal (a, b) 105 sbitmap a, b; 106{ 107 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 108} 109/* Zero all elements in a bitmap. */ 110 111void 112sbitmap_zero (bmap) 113 sbitmap bmap; 114{ 115 memset ((PTR) bmap->elms, 0, bmap->bytes); 116} 117 118/* Set all elements in a bitmap to ones. */ 119 120void 121sbitmap_ones (bmap) 122 sbitmap bmap; 123{ 124 unsigned int last_bit; 125 126 memset ((PTR) bmap->elms, -1, bmap->bytes); 127 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 134/* Zero a vector of N_VECS bitmaps. */ 135 136void 137sbitmap_vector_zero (bmap, n_vecs) 138 sbitmap *bmap; 139 unsigned int n_vecs; 140{ 141 unsigned int i; 142 143 for (i = 0; i < n_vecs; i++) 144 sbitmap_zero (bmap[i]); 145} 146 147/* Set a vector of N_VECS bitmaps to ones. */ 148 149void 150sbitmap_vector_ones (bmap, n_vecs) 151 sbitmap *bmap; 152 unsigned int n_vecs; 153{ 154 unsigned int i; 155 156 for (i = 0; i < n_vecs; i++) 157 sbitmap_ones (bmap[i]); 158} 159 160/* Set DST to be A union (B - C). 161 DST = A | (B & ~C). 162 Return non-zero if any change is made. */ 163 164int 165sbitmap_union_of_diff (dst, a, b, c) 166 sbitmap dst, a, b, c; 167{ 168 unsigned int i; 169 sbitmap_ptr dstp, ap, bp, cp; 170 int changed = 0; 171 172 for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; 173 i < dst->size; i++, dstp++) 174 { 175 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 176 177 if (*dstp != tmp) 178 { 179 changed = 1; 180 *dstp = tmp; 181 } 182 } 183 184 return changed; 185} 186 187/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 188 189void 190sbitmap_not (dst, src) 191 sbitmap dst, src; 192{ 193 unsigned int i; 194 sbitmap_ptr dstp, srcp; 195 196 for (dstp = dst->elms, srcp = src->elms, i = 0; i < dst->size; i++) 197 *dstp++ = ~(*srcp++); 198} 199 200/* Set the bits in DST to be the difference between the bits 201 in A and the bits in B. i.e. dst = a & (~b). */ 202 203void 204sbitmap_difference (dst, a, b) 205 sbitmap dst, a, b; 206{ 207 unsigned int i; 208 sbitmap_ptr dstp, ap, bp; 209 210 for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; i++) 211 *dstp++ = *ap++ & (~*bp++); 212} 213 214/* Set DST to be (A and B). 215 Return non-zero if any change is made. */ 216 217int 218sbitmap_a_and_b (dst, a, b) 219 sbitmap dst, a, b; 220{ 221 unsigned int i; 222 sbitmap_ptr dstp, ap, bp; 223 int changed = 0; 224 225 for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; 226 i++, dstp++) 227 { 228 SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 229 230 if (*dstp != tmp) 231 { 232 changed = 1; 233 *dstp = tmp; 234 } 235 } 236 237 return changed; 238} 239 240/* Set DST to be (A xor B)). 241 Return non-zero if any change is made. */ 242 243int 244sbitmap_a_xor_b (dst, a, b) 245 sbitmap dst, a, b; 246{ 247 unsigned int i; 248 sbitmap_ptr dstp, ap, bp; 249 int changed = 0; 250 251 for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; 252 i++, dstp++) 253 { 254 SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 255 256 if (*dstp != tmp) 257 { 258 changed = 1; 259 *dstp = tmp; 260 } 261 } 262 return changed; 263} 264 265/* Set DST to be (A or B)). 266 Return non-zero if any change is made. */ 267 268int 269sbitmap_a_or_b (dst, a, b) 270 sbitmap dst, a, b; 271{ 272 unsigned int i; 273 sbitmap_ptr dstp, ap, bp; 274 int changed = 0; 275 276 for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; 277 i++, dstp++) 278 { 279 SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 280 281 if (*dstp != tmp) 282 { 283 changed = 1; 284 *dstp = tmp; 285 } 286 } 287 288 return changed; 289} 290 291/* Return non-zero if A is a subset of B. */ 292 293int 294sbitmap_a_subset_b_p (a, b) 295 sbitmap a, b; 296{ 297 unsigned int i; 298 sbitmap_ptr ap, bp; 299 300 for (ap = a->elms, bp = b->elms, i = 0; i < a->size; i++, ap++, bp++) 301 if ((*ap | *bp) != *bp) 302 return 0; 303 304 return 1; 305} 306 307/* Set DST to be (A or (B and C)). 308 Return non-zero if any change is made. */ 309 310int 311sbitmap_a_or_b_and_c (dst, a, b, c) 312 sbitmap dst, a, b, c; 313{ 314 unsigned int i; 315 sbitmap_ptr dstp, ap, bp, cp; 316 int changed = 0; 317 318 for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; 319 i < dst->size; i++, dstp++) 320 { 321 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 322 323 if (*dstp != tmp) 324 { 325 changed = 1; 326 *dstp = tmp; 327 } 328 } 329 330 return changed; 331} 332 333/* Set DST to be (A and (B or C)). 334 Return non-zero if any change is made. */ 335 336int 337sbitmap_a_and_b_or_c (dst, a, b, c) 338 sbitmap dst, a, b, c; 339{ 340 unsigned int i; 341 sbitmap_ptr dstp, ap, bp, cp; 342 int changed = 0; 343 344 for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0; 345 i < dst->size; i++, dstp++) 346 { 347 SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 348 349 if (*dstp != tmp) 350 { 351 changed = 1; 352 *dstp = tmp; 353 } 354 } 355 356 return changed; 357} 358 359#ifdef IN_GCC 360/* Set the bitmap DST to the intersection of SRC of successors of 361 block number BB, using the new flow graph structures. */ 362 363void 364sbitmap_intersection_of_succs (dst, src, bb) 365 sbitmap dst; 366 sbitmap *src; 367 int bb; 368{ 369 basic_block b = BASIC_BLOCK (bb); 370 unsigned int set_size = dst->size; 371 edge e; 372 373 for (e = b->succ; e != 0; e = e->succ_next) 374 { 375 if (e->dest == EXIT_BLOCK_PTR) 376 continue; 377 378 sbitmap_copy (dst, src[e->dest->index]); 379 break; 380 } 381 382 if (e == 0) 383 sbitmap_ones (dst); 384 else 385 for (e = e->succ_next; e != 0; e = e->succ_next) 386 { 387 unsigned int i; 388 sbitmap_ptr p, r; 389 390 if (e->dest == EXIT_BLOCK_PTR) 391 continue; 392 393 p = src[e->dest->index]->elms; 394 r = dst->elms; 395 for (i = 0; i < set_size; i++) 396 *r++ &= *p++; 397 } 398} 399 400/* Set the bitmap DST to the intersection of SRC of predecessors of 401 block number BB, using the new flow graph structures. */ 402 403void 404sbitmap_intersection_of_preds (dst, src, bb) 405 sbitmap dst; 406 sbitmap *src; 407 int bb; 408{ 409 basic_block b = BASIC_BLOCK (bb); 410 unsigned int set_size = dst->size; 411 edge e; 412 413 for (e = b->pred; e != 0; e = e->pred_next) 414 { 415 if (e->src == ENTRY_BLOCK_PTR) 416 continue; 417 418 sbitmap_copy (dst, src[e->src->index]); 419 break; 420 } 421 422 if (e == 0) 423 sbitmap_ones (dst); 424 else 425 for (e = e->pred_next; e != 0; e = e->pred_next) 426 { 427 unsigned int i; 428 sbitmap_ptr p, r; 429 430 if (e->src == ENTRY_BLOCK_PTR) 431 continue; 432 433 p = src[e->src->index]->elms; 434 r = dst->elms; 435 for (i = 0; i < set_size; i++) 436 *r++ &= *p++; 437 } 438} 439 440/* Set the bitmap DST to the union of SRC of successors of 441 block number BB, using the new flow graph structures. */ 442 443void 444sbitmap_union_of_succs (dst, src, bb) 445 sbitmap dst; 446 sbitmap *src; 447 int bb; 448{ 449 basic_block b = BASIC_BLOCK (bb); 450 unsigned int set_size = dst->size; 451 edge e; 452 453 for (e = b->succ; e != 0; e = e->succ_next) 454 { 455 if (e->dest == EXIT_BLOCK_PTR) 456 continue; 457 458 sbitmap_copy (dst, src[e->dest->index]); 459 break; 460 } 461 462 if (e == 0) 463 sbitmap_zero (dst); 464 else 465 for (e = e->succ_next; e != 0; e = e->succ_next) 466 { 467 unsigned int i; 468 sbitmap_ptr p, r; 469 470 if (e->dest == EXIT_BLOCK_PTR) 471 continue; 472 473 p = src[e->dest->index]->elms; 474 r = dst->elms; 475 for (i = 0; i < set_size; i++) 476 *r++ |= *p++; 477 } 478} 479 480/* Set the bitmap DST to the union of SRC of predecessors of 481 block number BB, using the new flow graph structures. */ 482 483void 484sbitmap_union_of_preds (dst, src, bb) 485 sbitmap dst; 486 sbitmap *src; 487 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->pred; e != 0; e = e->pred_next) 494 { 495 if (e->src== ENTRY_BLOCK_PTR) 496 continue; 497 498 sbitmap_copy (dst, src[e->src->index]); 499 break; 500 } 501 502 if (e == 0) 503 sbitmap_zero (dst); 504 else 505 for (e = e->pred_next; e != 0; e = e->pred_next) 506 { 507 unsigned int i; 508 sbitmap_ptr p, r; 509 510 if (e->src == ENTRY_BLOCK_PTR) 511 continue; 512 513 p = src[e->src->index]->elms; 514 r = dst->elms; 515 for (i = 0; i < set_size; i++) 516 *r++ |= *p++; 517 } 518} 519#endif 520 521/* Return number of first bit set in the bitmap, -1 if none. */ 522 523int 524sbitmap_first_set_bit (bmap) 525 sbitmap bmap; 526{ 527 unsigned int n; 528 529 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; }); 530 return -1; 531} 532 533/* Return number of last bit set in the bitmap, -1 if none. */ 534 535int 536sbitmap_last_set_bit (bmap) 537 sbitmap bmap; 538{ 539 int i; 540 SBITMAP_ELT_TYPE *ptr = bmap->elms; 541 542 for (i = bmap->size - 1; i >= 0; i--) 543 { 544 SBITMAP_ELT_TYPE word = ptr[i]; 545 546 if (word != 0) 547 { 548 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 549 SBITMAP_ELT_TYPE mask 550 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 551 552 while (1) 553 { 554 if ((word & mask) != 0) 555 return index; 556 557 mask >>= 1; 558 index--; 559 } 560 } 561 } 562 563 return -1; 564} 565 566void 567dump_sbitmap (file, bmap) 568 FILE *file; 569 sbitmap bmap; 570{ 571 unsigned int i, n, j; 572 unsigned int set_size = bmap->size; 573 unsigned int total_bits = bmap->n_bits; 574 575 fprintf (file, " "); 576 for (i = n = 0; i < set_size && n < total_bits; i++) 577 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 578 { 579 if (n != 0 && n % 10 == 0) 580 fprintf (file, " "); 581 582 fprintf (file, "%d", 583 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 584 } 585 586 fprintf (file, "\n"); 587} 588 589void 590debug_sbitmap (bmap) 591 sbitmap bmap; 592{ 593 unsigned int i, pos; 594 595 fprintf (stderr, "n_bits = %d, set = {", bmap->n_bits); 596 597 for (pos = 30, i = 0; i < bmap->n_bits; i++) 598 if (TEST_BIT (bmap, i)) 599 { 600 if (pos > 70) 601 { 602 fprintf (stderr, "\n"); 603 pos = 0; 604 } 605 606 fprintf (stderr, "%d ", i); 607 pos += 1 + (i >= 10) + (i >= 100); 608 } 609 610 fprintf (stderr, "}\n"); 611} 612 613void 614dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps) 615 FILE *file; 616 const char *title, *subtitle; 617 sbitmap *bmaps; 618 int n_maps; 619{ 620 int bb; 621 622 fprintf (file, "%s\n", title); 623 for (bb = 0; bb < n_maps; bb++) 624 { 625 fprintf (file, "%s %d\n", subtitle, bb); 626 dump_sbitmap (file, bmaps[bb]); 627 } 628 629 fprintf (file, "\n"); 630} 631