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   for (ap = a->elms, bp = b->elms, i = 0; i < a->size; i++, ap++, bp++)
 269     if ((*ap | *bp) != *bp)
 270       return 0;
 271
 272   return 1;
 273 }
 274
 275 /* Set DST to be (A or (B and C)).
 276    Return non-zero if any change is made.  */
 277
 278 int
 279 sbitmap_a_or_b_and_c (dst, a, b, c)
 280      sbitmap dst, a, b, c;
 281 {
 282   unsigned int i;
 283   sbitmap_ptr dstp, ap, bp, cp;
 284   int changed = 0;
 285
 286   for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0;
 287        i < dst->size; i++, dstp++)
 288     {
 289       SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 290
 291       if (*dstp != tmp)
 292         {
 293           changed = 1;
 294           *dstp = tmp;
 295         }
 296     }
 297
 298   return changed;
 299 }
 300
 301 /* Set DST to be (A and (B or C)).
 302    Return non-zero if any change is made.  */
 303
 304 int
 305 sbitmap_a_and_b_or_c (dst, a, b, c)
 306      sbitmap dst, a, b, c;
 307 {
 308   unsigned int i;
 309   sbitmap_ptr dstp, ap, bp, cp;
 310   int changed = 0;
 311
 312   for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0;
 313        i < dst->size; i++, dstp++)
 314     {
 315       SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 316
 317       if (*dstp != tmp)
 318         {
 319           changed = 1;
 320           *dstp = tmp;
 321         }
 322     }
 323
 324   return changed;
 325 }
 326
 327 /* Set the bitmap DST to the intersection of SRC of successors of
 328    block number BB, using the new flow graph structures.  */
 329
 330 void
 331 sbitmap_intersection_of_succs (dst, src, bb)
 332      sbitmap dst;
 333      sbitmap *src;
 334      int bb;
 335 {
 336   basic_block b = BASIC_BLOCK (bb);
 337   unsigned int set_size = dst->size;
 338   edge e;
 339
 340   for (e = b->succ; e != 0; e = e->succ_next)
 341     {
 342       if (e->dest == EXIT_BLOCK_PTR)
 343         continue;
 344
 345       sbitmap_copy (dst, src[e->dest->index]);
 346       break;
 347     }
 348
 349   if (e == 0)
 350     sbitmap_ones (dst);
 351   else
 352     for (e = e->succ_next; e != 0; e = e->succ_next)
 353       {
 354         unsigned int i;
 355         sbitmap_ptr p, r;
 356
 357         if (e->dest == EXIT_BLOCK_PTR)
 358           continue;
 359
 360         p = src[e->dest->index]->elms;
 361         r = dst->elms;
 362         for (i = 0; i < set_size; i++)
 363           *r++ &= *p++;
 364       }
 365 }
 366
 367 /* Set the bitmap DST to the intersection of SRC of predecessors of
 368    block number BB, using the new flow graph structures.  */
 369
 370 void
 371 sbitmap_intersection_of_preds (dst, src, bb)
 372      sbitmap dst;
 373      sbitmap *src;
 374      int bb;
 375 {
 376   basic_block b = BASIC_BLOCK (bb);
 377   unsigned int set_size = dst->size;
 378   edge e;
 379
 380   for (e = b->pred; e != 0; e = e->pred_next)
 381     {
 382       if (e->src == ENTRY_BLOCK_PTR)
 383         continue;
 384
 385       sbitmap_copy (dst, src[e->src->index]);
 386       break;
 387     }
 388
 389   if (e == 0)
 390     sbitmap_ones (dst);
 391   else
 392     for (e = e->pred_next; e != 0; e = e->pred_next)
 393       {
 394         unsigned int i;
 395         sbitmap_ptr p, r;
 396
 397         if (e->src == ENTRY_BLOCK_PTR)
 398           continue;
 399
 400         p = src[e->src->index]->elms;
 401         r = dst->elms;
 402         for (i = 0; i < set_size; i++)
 403           *r++ &= *p++;
 404       }
 405 }
 406
 407 /* Set the bitmap DST to the union of SRC of successors of
 408    block number BB, using the new flow graph structures.  */
 409
 410 void
 411 sbitmap_union_of_succs (dst, src, bb)
 412      sbitmap dst;
 413      sbitmap *src;
 414      int bb;
 415 {
 416   basic_block b = BASIC_BLOCK (bb);
 417   unsigned int set_size = dst->size;
 418   edge e;
 419
 420   for (e = b->succ; e != 0; e = e->succ_next)
 421     {
 422       if (e->dest == EXIT_BLOCK_PTR)
 423         continue;
 424
 425       sbitmap_copy (dst, src[e->dest->index]);
 426       break;
 427     }
 428
 429   if (e == 0)
 430     sbitmap_zero (dst);
 431   else
 432     for (e = e->succ_next; e != 0; e = e->succ_next)
 433       {
 434         unsigned int i;
 435         sbitmap_ptr p, r;
 436
 437         if (e->dest == EXIT_BLOCK_PTR)
 438           continue;
 439
 440         p = src[e->dest->index]->elms;
 441         r = dst->elms;
 442         for (i = 0; i < set_size; i++)
 443           *r++ |= *p++;
 444       }
 445 }
 446
 447 /* Set the bitmap DST to the union of SRC of predecessors of
 448    block number BB, using the new flow graph structures.  */
 449
 450 void
 451 sbitmap_union_of_preds (dst, src, bb)
 452      sbitmap dst;
 453      sbitmap *src;
 454      int bb;
 455 {
 456   basic_block b = BASIC_BLOCK (bb);
 457   unsigned int set_size = dst->size;
 458   edge e;
 459
 460   for (e = b->pred; e != 0; e = e->pred_next)
 461     {
 462       if (e->src== ENTRY_BLOCK_PTR)
 463         continue;
 464
 465       sbitmap_copy (dst, src[e->src->index]);
 466       break;
 467     }
 468
 469   if (e == 0)
 470     sbitmap_zero (dst);
 471   else
 472     for (e = e->pred_next; e != 0; e = e->pred_next)
 473       {
 474         unsigned int i;
 475         sbitmap_ptr p, r;
 476
 477         if (e->src == ENTRY_BLOCK_PTR)
 478           continue;
 479
 480         p = src[e->src->index]->elms;
 481         r = dst->elms;
 482         for (i = 0; i < set_size; i++)
 483           *r++ |= *p++;
 484       }
 485 }
 486
 487 /* Return number of first bit set in the bitmap, -1 if none.  */
 488
 489 int
 490 sbitmap_first_set_bit (bmap)
 491      sbitmap bmap;
 492 {
 493   unsigned int n;
 494
 495   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; });
 496   return -1;
 497 }
 498
 499 /* Return number of last bit set in the bitmap, -1 if none.  */
 500
 501 int
 502 sbitmap_last_set_bit (bmap)
 503      sbitmap bmap;
 504 {
 505   int i;
 506   SBITMAP_ELT_TYPE *ptr = bmap->elms;
 507
 508   for (i = bmap->size - 1; i >= 0; i--)
 509     {
 510       SBITMAP_ELT_TYPE word = ptr[i];
 511
 512       if (word != 0)
 513         {
 514           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 515           SBITMAP_ELT_TYPE mask
 516             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 517
 518           while (1)
 519             {
 520               if ((word & mask) != 0)
 521                 return index;
 522
 523               mask >>= 1;
 524               index--;
 525             }
 526         }
 527     }
 528
 529   return -1;
 530 }
 531
 532 void
 533 dump_sbitmap (file, bmap)
 534      FILE *file;
 535      sbitmap bmap;
 536 {
 537   unsigned int i, n, j;
 538   unsigned int set_size = bmap->size;
 539   unsigned int total_bits = bmap->n_bits;
 540
 541   fprintf (file, "  ");
 542   for (i = n = 0; i < set_size && n < total_bits; i++)
 543     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 544       {
 545         if (n != 0 && n % 10 == 0)
 546           fprintf (file, " ");
 547
 548         fprintf (file, "%d",
 549                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 550       }
 551
 552   fprintf (file, "\n");
 553 }
 554
 555 void
 556 debug_sbitmap (bmap)
 557      sbitmap bmap;
 558 {
 559   unsigned int i, pos;
 560
 561   fprintf (stderr, "n_bits = %d, set = {", bmap->n_bits);
 562
 563   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 564     if (TEST_BIT (bmap, i))
 565       {
 566         if (pos > 70)
 567           {
 568             fprintf (stderr, "\n");
 569             pos = 0;
 570           }
 571
 572         fprintf (stderr, "%d ", i);
 573         pos += 1 + (i >= 10) + (i >= 100);
 574       }
 575
 576   fprintf (stderr, "}\n");
 577 }
 578
 579 void
 580 dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps)
 581      FILE *file;
 582      const char *title, *subtitle;
 583      sbitmap *bmaps;
 584      int n_maps;
 585 {
 586   int bb;
 587
 588   fprintf (file, "%s\n", title);
 589   for (bb = 0; bb < n_maps; bb++)
 590     {
 591       fprintf (file, "%s %d\n", subtitle, bb);
 592       dump_sbitmap (file, bmaps[bb]);
 593     }
 594
 595   fprintf (file, "\n");
 596 }