gcc/sbitmap.c

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