gcc/sbitmap.c

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