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