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