gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999 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      int n_elms;
  34 {
  35   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      int n_vecs, n_elms;
  54 {
  55   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;
  80        i < n_vecs;
  81        i++, offset += elm_bytes)
  82     {
  83       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
  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   bzero ((char *) bmap->elms, bmap->bytes);
 110 }
 111
 112 /* Set to ones all elements in a bitmap.  */
 113
 114 void
 115 sbitmap_ones (bmap)
 116      sbitmap bmap;
 117 {
 118   unsigned int last_bit;
 119
 120   memset (bmap->elms, -1, bmap->bytes);
 121
 122   last_bit = bmap->n_bits % (unsigned) SBITMAP_ELT_BITS;
 123   if (last_bit)
 124     {
 125       bmap->elms[bmap->size - 1]
 126         = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 127     }
 128 }
 129
 130 /* Zero a vector of N_VECS bitmaps.  */
 131
 132 void
 133 sbitmap_vector_zero (bmap, n_vecs)
 134      sbitmap *bmap;
 135      int n_vecs;
 136 {
 137   int i;
 138
 139   for (i = 0; i < n_vecs; i++)
 140     sbitmap_zero (bmap[i]);
 141 }
 142
 143 /* Set to ones a vector of N_VECS bitmaps.  */
 144
 145 void
 146 sbitmap_vector_ones (bmap, n_vecs)
 147      sbitmap *bmap;
 148      int n_vecs;
 149 {
 150   int i;
 151
 152   for (i = 0; i < n_vecs; i++)
 153     sbitmap_ones (bmap[i]);
 154 }
 155
 156 /* Set DST to be A union (B - C).
 157    DST = A | (B & ~C).
 158    Return non-zero if any change is made.  */
 159
 160 int
 161 sbitmap_union_of_diff (dst, a, b, c)
 162      sbitmap dst, a, b, c;
 163 {
 164   int i,changed;
 165   sbitmap_ptr dstp, ap, bp, cp;
 166
 167   changed = 0;
 168   dstp = dst->elms;
 169   ap = a->elms;
 170   bp = b->elms;
 171   cp = c->elms;
 172   for (i = 0; i < dst->size; i++)
 173     {
 174       SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp);
 175       if (*dstp != tmp)
 176         changed = 1;
 177       *dstp = tmp;
 178       dstp++; ap++; bp++; cp++;
 179     }
 180   return changed;
 181 }
 182
 183 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 184
 185 void
 186 sbitmap_not (dst, src)
 187      sbitmap dst, src;
 188 {
 189   int i;
 190   sbitmap_ptr dstp, ap;
 191
 192   dstp = dst->elms;
 193   ap = src->elms;
 194   for (i = 0; i < dst->size; i++)
 195     {
 196       SBITMAP_ELT_TYPE tmp = ~(*ap);
 197       *dstp = tmp;
 198       dstp++; ap++;
 199     }
 200 }
 201
 202 /* Set the bits in DST to be the difference between the bits
 203    in A and the bits in B. i.e. dst = a - b.
 204    The - operator is implemented as a & (~b).  */
 205
 206 void
 207 sbitmap_difference (dst, a, b)
 208      sbitmap dst, a, b;
 209 {
 210   int i;
 211   sbitmap_ptr dstp, ap, bp;
 212
 213   dstp = dst->elms;
 214   ap = a->elms;
 215   bp = b->elms;
 216   for (i = 0; i < dst->size; i++)
 217     *dstp++ = *ap++ & (~*bp++);
 218 }
 219
 220 /* Set DST to be (A and B).
 221    Return non-zero if any change is made.  */
 222
 223 int
 224 sbitmap_a_and_b (dst, a, b)
 225      sbitmap dst, a, b;
 226 {
 227   int i,changed;
 228   sbitmap_ptr dstp, ap, bp;
 229
 230   changed = 0;
 231   dstp = dst->elms;
 232   ap = a->elms;
 233   bp = b->elms;
 234   for (i = 0; i < dst->size; i++)
 235     {
 236       SBITMAP_ELT_TYPE tmp = *ap & *bp;
 237       if (*dstp != tmp)
 238         changed = 1;
 239       *dstp = tmp;
 240       dstp++; ap++; bp++;
 241     }
 242   return changed;
 243 }
 244 /* Set DST to be (A or B)).
 245    Return non-zero if any change is made.  */
 246
 247 int
 248 sbitmap_a_or_b (dst, a, b)
 249      sbitmap dst, a, b;
 250 {
 251   int i,changed;
 252   sbitmap_ptr dstp, ap, bp;
 253
 254   changed = 0;
 255   dstp = dst->elms;
 256   ap = a->elms;
 257   bp = b->elms;
 258   for (i = 0; i < dst->size; i++)
 259     {
 260       SBITMAP_ELT_TYPE tmp = *ap | *bp;
 261       if (*dstp != tmp)
 262         changed = 1;
 263       *dstp = tmp;
 264       dstp++; ap++; bp++;
 265     }
 266   return changed;
 267 }
 268 /* Return non-zero if A is a subset of B.  */
 269
 270 int
 271 sbitmap_a_subset_b_p (a, b)
 272      sbitmap a, b;
 273 {
 274   int i;
 275   sbitmap_ptr ap, bp;
 276
 277   ap = a->elms;
 278   bp = b->elms;
 279   for (i = 0; i < a->size; i++)
 280     {
 281       if ((*ap | *bp) != *bp)
 282         return 0;
 283       ap++; bp++;
 284     }
 285   return 1;
 286 }
 287
 288 /* Set DST to be (A or (B and C)).
 289    Return non-zero if any change is made.  */
 290
 291 int
 292 sbitmap_a_or_b_and_c (dst, a, b, c)
 293      sbitmap dst, a, b, c;
 294 {
 295   int i,changed;
 296   sbitmap_ptr dstp, ap, bp, cp;
 297
 298   changed = 0;
 299   dstp = dst->elms;
 300   ap = a->elms;
 301   bp = b->elms;
 302   cp = c->elms;
 303   for (i = 0; i < dst->size; i++)
 304     {
 305       SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp);
 306       if (*dstp != tmp)
 307         changed = 1;
 308       *dstp = tmp;
 309       dstp++; ap++; bp++; cp++;
 310     }
 311   return changed;
 312 }
 313
 314 /* Set DST to be (A ann (B or C)).
 315    Return non-zero if any change is made.  */
 316
 317 int
 318 sbitmap_a_and_b_or_c (dst, a, b, c)
 319      sbitmap dst, a, b, c;
 320 {
 321   int i,changed;
 322   sbitmap_ptr dstp, ap, bp, cp;
 323
 324   changed = 0;
 325   dstp = dst->elms;
 326   ap = a->elms;
 327   bp = b->elms;
 328   cp = c->elms;
 329   for (i = 0; i < dst->size; i++)
 330     {
 331       SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp);
 332       if (*dstp != tmp)
 333         changed = 1;
 334       *dstp = tmp;
 335       dstp++; ap++; bp++; cp++;
 336     }
 337   return changed;
 338 }
 339
 340 /* Set the bitmap DST to the intersection of SRC of successors of
 341    block number BB, using the new flow graph structures.  */
 342
 343 void
 344 sbitmap_intersection_of_succs (dst, src, bb)
 345      sbitmap dst;
 346      sbitmap *src;
 347      int bb;
 348 {
 349   basic_block b = BASIC_BLOCK (bb);
 350   edge e = b->succ;
 351   int set_size = dst->size;
 352
 353   for ( ; e != NULL; e = e->succ_next)
 354     {
 355       if (e->dest == EXIT_BLOCK_PTR)
 356         continue;
 357       sbitmap_copy (dst, src[e->dest->index]);
 358       break;
 359     }
 360   if (e == NULL)
 361     sbitmap_ones (dst);
 362   else
 363     {
 364       for ( e = e->succ_next; e != NULL; e = e->succ_next)
 365         {
 366           int i;
 367           sbitmap_ptr p,r;
 368
 369           if (e->dest == EXIT_BLOCK_PTR)
 370             continue;
 371
 372           p = src[e->dest->index]->elms;
 373           r = dst->elms;
 374           for (i = 0; i < set_size; i++)
 375             *r++ &= *p++;
 376         }
 377     }
 378 }
 379
 380 /* Set the bitmap DST to the intersection of SRC of predecessors of
 381    block number BB, using the new flow graph structures.  */
 382
 383 void
 384 sbitmap_intersection_of_preds (dst, src, bb)
 385      sbitmap dst;
 386      sbitmap *src;
 387      int bb;
 388 {
 389   basic_block b = BASIC_BLOCK (bb);
 390   edge e = b->pred;
 391   int set_size = dst->size;
 392
 393   for ( ; e != NULL; e = e->pred_next)
 394     {
 395       if (e->src== ENTRY_BLOCK_PTR)
 396         continue;
 397       sbitmap_copy (dst, src[e->src->index]);
 398       break;
 399     }
 400   if (e == NULL)
 401     sbitmap_ones (dst);
 402   else
 403     {
 404       for ( e = e->pred_next; e != NULL; e = e->pred_next)
 405         {
 406           int i;
 407           sbitmap_ptr p,r;
 408
 409           if (e->src == ENTRY_BLOCK_PTR)
 410             continue;
 411
 412           p = src[e->src->index]->elms;
 413           r = dst->elms;
 414           for (i = 0; i < set_size; i++)
 415             *r++ &= *p++;
 416         }
 417     }
 418 }
 419
 420 /* Set the bitmap DST to the union of SRC of successors of
 421    block number BB, using the new flow graph structures.  */
 422
 423 void
 424 sbitmap_union_of_succs (dst, src, bb)
 425      sbitmap dst;
 426      sbitmap *src;
 427      int bb;
 428 {
 429   basic_block b = BASIC_BLOCK (bb);
 430   edge e = b->succ;
 431   int set_size = dst->size;
 432
 433   for ( ; e != NULL; e = e->succ_next)
 434     {
 435       if (e->dest == EXIT_BLOCK_PTR)
 436         continue;
 437       sbitmap_copy (dst, src[e->dest->index]);
 438       break;
 439     }
 440   if (e == NULL)
 441     sbitmap_zero (dst);
 442   else
 443     {
 444       for ( e = e->succ_next; e != NULL; e = e->succ_next)
 445         {
 446           int i;
 447           sbitmap_ptr p,r;
 448
 449           if (e->dest == EXIT_BLOCK_PTR)
 450             continue;
 451
 452           p = src[e->dest->index]->elms;
 453           r = dst->elms;
 454           for (i = 0; i < set_size; i++)
 455             *r++ |= *p++;
 456         }
 457     }
 458 }
 459
 460 /* Set the bitmap DST to the union of SRC of predecessors of
 461    block number BB, using the new flow graph structures.  */
 462
 463 void
 464 sbitmap_union_of_preds (dst, src, bb)
 465      sbitmap dst;
 466      sbitmap *src;
 467      int bb;
 468 {
 469   basic_block b = BASIC_BLOCK (bb);
 470   edge e = b->pred;
 471   int set_size = dst->size;
 472
 473   for ( ; e != NULL; e = e->pred_next)
 474     {
 475       if (e->src== ENTRY_BLOCK_PTR)
 476         continue;
 477       sbitmap_copy (dst, src[e->src->index]);
 478       break;
 479     }
 480   if (e == NULL)
 481     sbitmap_zero (dst);
 482   else
 483     {
 484       for ( e = e->pred_next; e != NULL; e = e->pred_next)
 485         {
 486           int i;
 487           sbitmap_ptr p,r;
 488
 489           if (e->src == ENTRY_BLOCK_PTR)
 490             continue;
 491
 492           p = src[e->src->index]->elms;
 493           r = dst->elms;
 494           for (i = 0; i < set_size; i++)
 495             *r++ |= *p++;
 496         }
 497     }
 498 }
 499
 500 /* Return number of first bit set in the bitmap, -1 if none.  */
 501
 502 int
 503 sbitmap_first_set_bit (bmap)
 504      sbitmap bmap;
 505 {
 506   int n;
 507   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, { return n; });
 508   return -1;
 509 }
 510
 511 /* Return number of last bit set in the bitmap, -1 if none.  */
 512
 513 int
 514 sbitmap_last_set_bit (bmap)
 515      sbitmap bmap;
 516 {
 517   int i;
 518   SBITMAP_ELT_TYPE *ptr = bmap->elms;
 519   for (i = bmap->size - 1; i >= 0; i--)
 520     {
 521       SBITMAP_ELT_TYPE word = ptr[i];
 522       if (word)
 523       {
 524         int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 525         SBITMAP_ELT_TYPE mask = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 526         while (1)
 527           {
 528             if (word & mask)
 529               return index;
 530             mask >>= 1;
 531             index--;
 532           }
 533       }
 534     }
 535   return -1;
 536 }
 537
 538 void
 539 dump_sbitmap (file, bmap)
 540      FILE *file;
 541      sbitmap bmap;
 542 {
 543   int i,j,n;
 544   int set_size = bmap->size;
 545   int total_bits = bmap->n_bits;
 546
 547   fprintf (file, "  ");
 548   for (i = n = 0; i < set_size && n < total_bits; i++)
 549     {
 550       for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 551         {
 552           if (n != 0 && n % 10 == 0)
 553             fprintf (file, " ");
 554           fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0);
 555         }
 556     }
 557   fprintf (file, "\n");
 558 }
 559
 560 void
 561 dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps)
 562      FILE *file;
 563      const char *title, *subtitle;
 564      sbitmap *bmaps;
 565      int n_maps;
 566 {
 567   int bb;
 568
 569   fprintf (file, "%s\n", title);
 570   for (bb = 0; bb < n_maps; bb++)
 571     {
 572       fprintf (file, "%s %d\n", subtitle, bb);
 573       dump_sbitmap (file, bmaps[bb]);
 574     }
 575   fprintf (file, "\n");
 576 }