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 "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   bcopy ((PTR) src->elms, (PTR) dst->elms,
 100          sizeof (SBITMAP_ELT_TYPE) * dst->size);
 101 }
 102
 103 /* Zero all elements in a bitmap.  */
 104
 105 void
 106 sbitmap_zero (bmap)
 107      sbitmap bmap;
 108 {
 109   memset ((PTR) bmap->elms, 0, bmap->bytes);
 110 }
 111
 112 /* Set all elements in a bitmap to ones.  */
 113
 114 void
 115 sbitmap_ones (bmap)
 116      sbitmap bmap;
 117 {
 118   unsigned int last_bit;
 119
 120   memset ((PTR) bmap->elms, -1, bmap->bytes);
 121
 122   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 123   if (last_bit)
 124     bmap->elms[bmap->size - 1]
 125       = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 126 }
 127
 128 /* Zero a vector of N_VECS bitmaps.  */
 129
 130 void
 131 sbitmap_vector_zero (bmap, n_vecs)
 132      sbitmap *bmap;
 133      unsigned int n_vecs;
 134 {
 135   unsigned int i;
 136
 137   for (i = 0; i < n_vecs; i++)
 138     sbitmap_zero (bmap[i]);
 139 }
 140
 141 /* Set a vector of N_VECS bitmaps to ones.  */
 142
 143 void
 144 sbitmap_vector_ones (bmap, n_vecs)
 145      sbitmap *bmap;
 146      unsigned int n_vecs;
 147 {
 148   unsigned int i;
 149
 150   for (i = 0; i < n_vecs; i++)
 151     sbitmap_ones (bmap[i]);
 152 }
 153
 154 /* Set DST to be A union (B - C).
 155    DST = A | (B & ~C).
 156    Return non-zero if any change is made.  */
 157
 158 int
 159 sbitmap_union_of_diff (dst, a, b, c)
 160      sbitmap dst, a, b, c;
 161 {
 162   unsigned int i;
 163   sbitmap_ptr dstp, ap, bp, cp;
 164   int changed = 0;
 165
 166   for (dstp = dst->elms, ap = a->elms, bp = b->elms, cp = c->elms, i = 0;
 167        i < dst->size; i++, dstp++)
 168     {
 169       SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 170
 171       if (*dstp != tmp)
 172         {
 173           changed = 1;
 174           *dstp = tmp;
 175         }
 176     }
 177
 178   return changed;
 179 }
 180
 181 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 182
 183 void
 184 sbitmap_not (dst, src)
 185      sbitmap dst, src;
 186 {
 187   unsigned int i;
 188   sbitmap_ptr dstp, srcp;
 189
 190   for (dstp = dst->elms, srcp = src->elms, i = 0; i < dst->size; i++)
 191     *dstp++ = ~(*srcp++);
 192 }
 193
 194 /* Set the bits in DST to be the difference between the bits
 195    in A and the bits in B. i.e. dst = a & (~b).  */
 196
 197 void
 198 sbitmap_difference (dst, a, b)
 199      sbitmap dst, a, b;
 200 {
 201   unsigned int i;
 202   sbitmap_ptr dstp, ap, bp;
 203
 204   for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size; i++)
 205     *dstp++ = *ap++ & (~*bp++);
 206 }
 207
 208 /* Set DST to be (A and B).
 209    Return non-zero if any change is made.  */
 210
 211 int
 212 sbitmap_a_and_b (dst, a, b)
 213      sbitmap dst, a, b;
 214 {
 215   unsigned int i;
 216   sbitmap_ptr dstp, ap, bp;
 217   int changed = 0;
 218
 219   for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size;
 220        i++, dstp++)
 221     {
 222       SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 223
 224       if (*dstp != tmp)
 225         {
 226           changed = 1;
 227           *dstp = tmp;
 228         }
 229     }
 230
 231   return changed;
 232 }
 233
 234 /* Set DST to be (A or B)).
 235    Return non-zero if any change is made.  */
 236
 237 int
 238 sbitmap_a_or_b (dst, a, b)
 239      sbitmap dst, a, b;
 240 {
 241   unsigned int i;
 242   sbitmap_ptr dstp, ap, bp;
 243   int changed = 0;
 244
 245   for (dstp = dst->elms, ap = a->elms, bp = b->elms, i = 0; i < dst->size;
 246        i++, dstp++)
 247     {
 248       SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 249
 250       if (*dstp != tmp)
 251         {
 252           changed = 1;
 253           *dstp = tmp;
 254         }
 255     }
 256
 257   return changed;
 258 }
 259
 260 /* Return non-zero if A is a subset of B.  */
 261
 262 int
 263 sbitmap_a_subset_b_p (a, b)
 264      sbitmap a, b;
 265 {
 266   unsigned int i;
 267   sbitmap_ptr ap, bp;
 268
 269   for (ap = a->elms, bp = b->elms, i = 0; i < a->size; i++, ap++, bp++)
 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 }