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
 269 /* Set DST to be (A or (B and C)).
 270    Return non-zero if any change is made.  */
 271
 272 int
 273 sbitmap_a_or_b_and_c (dst, a, b, c)
 274      sbitmap dst, a, b, c;
 275 {
 276   int i,changed;
 277   sbitmap_ptr dstp, ap, bp, cp;
 278
 279   changed = 0;
 280   dstp = dst->elms;
 281   ap = a->elms;
 282   bp = b->elms;
 283   cp = c->elms;
 284   for (i = 0; i < dst->size; i++)
 285     {
 286       SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp);
 287       if (*dstp != tmp)
 288         changed = 1;
 289       *dstp = tmp;
 290       dstp++; ap++; bp++; cp++;
 291     }
 292   return changed;
 293 }
 294
 295 /* Set DST to be (A ann (B or C)).
 296    Return non-zero if any change is made.  */
 297
 298 int
 299 sbitmap_a_and_b_or_c (dst, a, b, c)
 300      sbitmap dst, a, b, c;
 301 {
 302   int i,changed;
 303   sbitmap_ptr dstp, ap, bp, cp;
 304
 305   changed = 0;
 306   dstp = dst->elms;
 307   ap = a->elms;
 308   bp = b->elms;
 309   cp = c->elms;
 310   for (i = 0; i < dst->size; i++)
 311     {
 312       SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp);
 313       if (*dstp != tmp)
 314         changed = 1;
 315       *dstp = tmp;
 316       dstp++; ap++; bp++; cp++;
 317     }
 318   return changed;
 319 }
 320
 321 /* Set the bitmap DST to the intersection of SRC of all predecessors or
 322    successors of block number BB (PRED_SUCC says which).  */
 323
 324 void
 325 sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ)
 326      sbitmap dst;
 327      sbitmap *src;
 328      int bb;
 329      int_list_ptr *pred_succ;
 330 {
 331   int_list_ptr ps;
 332   int ps_bb;
 333   int set_size = dst->size;
 334
 335   ps = pred_succ[bb];
 336
 337   /* It is possible that there are no predecessors(/successors).
 338      This can happen for example in unreachable code.  */
 339
 340   if (ps == NULL)
 341     {
 342       /* In APL-speak this is the `and' reduction of the empty set and thus
 343          the result is the identity for `and'.  */
 344       sbitmap_ones (dst);
 345       return;
 346     }
 347
 348   /* Set result to first predecessor/successor.  */
 349
 350   for ( ; ps != NULL; ps = ps->next)
 351     {
 352       ps_bb = INT_LIST_VAL (ps);
 353       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 354         continue;
 355       sbitmap_copy (dst, src[ps_bb]);
 356       /* Break out since we're only doing first predecessor.  */
 357       break;
 358     }
 359   if (ps == NULL)
 360     return;
 361
 362   /* Now do the remaining predecessors/successors.  */
 363
 364   for (ps = ps->next; ps != NULL; ps = ps->next)
 365     {
 366       int i;
 367       sbitmap_ptr p,r;
 368
 369       ps_bb = INT_LIST_VAL (ps);
 370       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 371         continue;
 372
 373       p = src[ps_bb]->elms;
 374       r = dst->elms;
 375
 376       for (i = 0; i < set_size; i++)
 377         *r++ &= *p++;
 378     }
 379 }
 380
 381 /* Set the bitmap DST to the union of SRC of all predecessors/successors of
 382    block number BB.  */
 383
 384 void
 385 sbitmap_union_of_predsucc (dst, src, bb, pred_succ)
 386      sbitmap dst;
 387      sbitmap *src;
 388      int bb;
 389      int_list_ptr *pred_succ;
 390 {
 391   int_list_ptr ps;
 392   int ps_bb;
 393   int set_size = dst->size;
 394
 395   ps = pred_succ[bb];
 396
 397   /* It is possible that there are no predecessors(/successors).
 398      This can happen for example in unreachable code.  */
 399
 400   if (ps == NULL)
 401     {
 402       /* In APL-speak this is the `or' reduction of the empty set and thus
 403          the result is the identity for `or'.  */
 404       sbitmap_zero (dst);
 405       return;
 406     }
 407
 408   /* Set result to first predecessor/successor.  */
 409
 410   for ( ; ps != NULL; ps = ps->next)
 411     {
 412       ps_bb = INT_LIST_VAL (ps);
 413       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 414         continue;
 415       sbitmap_copy (dst, src[ps_bb]);
 416       /* Break out since we're only doing first predecessor.  */
 417       break;
 418     }
 419   if (ps == NULL)
 420     return;
 421
 422   /* Now do the remaining predecessors/successors.  */
 423
 424   for (ps = ps->next; ps != NULL; ps = ps->next)
 425     {
 426       int i;
 427       sbitmap_ptr p,r;
 428
 429       ps_bb = INT_LIST_VAL (ps);
 430       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 431         continue;
 432
 433       p = src[ps_bb]->elms;
 434       r = dst->elms;
 435
 436       for (i = 0; i < set_size; i++)
 437         *r++ |= *p++;
 438     }
 439 }
 440
 441 /* Set the bitmap DST to the intersection of SRC of successors of
 442    block number BB, using the new flow graph structures.  */
 443
 444 void
 445 sbitmap_intersection_of_succs (dst, src, bb)
 446      sbitmap dst;
 447      sbitmap *src;
 448      int bb;
 449 {
 450   basic_block b = BASIC_BLOCK (bb);
 451   edge e = b->succ;
 452   int set_size = dst->size;
 453
 454   for ( ; e != NULL; e = e->succ_next)
 455     {
 456       if (e->dest == EXIT_BLOCK_PTR)
 457         continue;
 458       sbitmap_copy (dst, src[e->dest->index]);
 459       break;
 460     }
 461   if (e == NULL)
 462     sbitmap_ones (dst);
 463   else
 464     {
 465       for ( e = e->succ_next; e != NULL; e = e->succ_next)
 466         {
 467           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
 481 /* Set the bitmap DST to the intersection of SRC of predecessors of
 482    block number BB, using the new flow graph structures.  */
 483
 484 void
 485 sbitmap_intersection_of_preds (dst, src, bb)
 486      sbitmap dst;
 487      sbitmap *src;
 488      int bb;
 489 {
 490   basic_block b = BASIC_BLOCK (bb);
 491   edge e = b->pred;
 492   int set_size = dst->size;
 493
 494   for ( ; e != NULL; e = e->pred_next)
 495     {
 496       if (e->src== ENTRY_BLOCK_PTR)
 497         continue;
 498       sbitmap_copy (dst, src[e->src->index]);
 499       break;
 500     }
 501   if (e == NULL)
 502     sbitmap_ones (dst);
 503   else
 504     {
 505       for ( e = e->pred_next; e != NULL; e = e->pred_next)
 506         {
 507           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 }
 520
 521 /* Set the bitmap DST to the union of SRC of successors of
 522    block number BB, using the new flow graph structures.  */
 523
 524 void
 525 sbitmap_union_of_succs (dst, src, bb)
 526      sbitmap dst;
 527      sbitmap *src;
 528      int bb;
 529 {
 530   basic_block b = BASIC_BLOCK (bb);
 531   edge e = b->succ;
 532   int set_size = dst->size;
 533
 534   for ( ; e != NULL; e = e->succ_next)
 535     {
 536       if (e->dest == EXIT_BLOCK_PTR)
 537         continue;
 538       sbitmap_copy (dst, src[e->dest->index]);
 539       break;
 540     }
 541   if (e == NULL)
 542     sbitmap_zero (dst);
 543   else
 544     {
 545       for ( e = e->succ_next; e != NULL; e = e->succ_next)
 546         {
 547           int i;
 548           sbitmap_ptr p,r;
 549
 550           if (e->dest == EXIT_BLOCK_PTR)
 551             continue;
 552
 553           p = src[e->dest->index]->elms;
 554           r = dst->elms;
 555           for (i = 0; i < set_size; i++)
 556             *r++ |= *p++;
 557         }
 558     }
 559 }
 560
 561 /* Set the bitmap DST to the union of SRC of predecessors of
 562    block number BB, using the new flow graph structures.  */
 563
 564 void
 565 sbitmap_union_of_preds (dst, src, bb)
 566      sbitmap dst;
 567      sbitmap *src;
 568      int bb;
 569 {
 570   basic_block b = BASIC_BLOCK (bb);
 571   edge e = b->pred;
 572   int set_size = dst->size;
 573
 574   for ( ; e != NULL; e = e->pred_next)
 575     {
 576       if (e->src== ENTRY_BLOCK_PTR)
 577         continue;
 578       sbitmap_copy (dst, src[e->src->index]);
 579       break;
 580     }
 581   if (e == NULL)
 582     sbitmap_zero (dst);
 583   else
 584     {
 585       for ( e = e->pred_next; e != NULL; e = e->pred_next)
 586         {
 587           int i;
 588           sbitmap_ptr p,r;
 589
 590           if (e->src == ENTRY_BLOCK_PTR)
 591             continue;
 592
 593           p = src[e->src->index]->elms;
 594           r = dst->elms;
 595           for (i = 0; i < set_size; i++)
 596             *r++ |= *p++;
 597         }
 598     }
 599 }
 600
 601 void
 602 dump_sbitmap (file, bmap)
 603      FILE *file;
 604      sbitmap bmap;
 605 {
 606   int i,j,n;
 607   int set_size = bmap->size;
 608   int total_bits = bmap->n_bits;
 609
 610   fprintf (file, "  ");
 611   for (i = n = 0; i < set_size && n < total_bits; i++)
 612     {
 613       for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 614         {
 615           if (n != 0 && n % 10 == 0)
 616             fprintf (file, " ");
 617           fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0);
 618         }
 619     }
 620   fprintf (file, "\n");
 621 }
 622
 623 void
 624 dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps)
 625      FILE *file;
 626      const char *title, *subtitle;
 627      sbitmap *bmaps;
 628      int n_maps;
 629 {
 630   int bb;
 631
 632   fprintf (file, "%s\n", title);
 633   for (bb = 0; bb < n_maps; bb++)
 634     {
 635       fprintf (file, "%s %d\n", subtitle, bb);
 636       dump_sbitmap (file, bmaps[bb]);
 637     }
 638   fprintf (file, "\n");
 639 }