gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999, 2000 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 /* Zero all elements in a bitmap.  */
 110
 111 void
 112 sbitmap_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
 120 void
 121 sbitmap_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
 136 void
 137 sbitmap_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
 149 void
 150 sbitmap_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
 164 int
 165 sbitmap_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
 189 void
 190 sbitmap_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
 203 void
 204 sbitmap_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
 217 int
 218 sbitmap_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
 243 int
 244 sbitmap_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
 268 int
 269 sbitmap_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
 293 int
 294 sbitmap_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
 310 int
 311 sbitmap_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
 336 int
 337 sbitmap_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
 363 void
 364 sbitmap_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
 403 void
 404 sbitmap_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
 443 void
 444 sbitmap_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
 483 void
 484 sbitmap_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
 523 int
 524 sbitmap_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
 535 int
 536 sbitmap_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
 566 void
 567 dump_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
 589 void
 590 debug_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
 613 void
 614 dump_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 }