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 (src->elms, dst->elms, 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 ((char *) bmap->elms, bmap->bytes);
 109 }
 110
 111 /* Set to ones all elements in a bitmap.  */
 112
 113 void
 114 sbitmap_ones (bmap)
 115      sbitmap bmap;
 116 {
 117   memset (bmap->elms, -1, bmap->bytes);
 118 }
 119
 120 /* Zero a vector of N_VECS bitmaps.  */
 121
 122 void
 123 sbitmap_vector_zero (bmap, n_vecs)
 124      sbitmap *bmap;
 125      int n_vecs;
 126 {
 127   int i;
 128
 129   for (i = 0; i < n_vecs; i++)
 130     sbitmap_zero (bmap[i]);
 131 }
 132
 133 /* Set to ones a vector of N_VECS bitmaps.  */
 134
 135 void
 136 sbitmap_vector_ones (bmap, n_vecs)
 137      sbitmap *bmap;
 138      int n_vecs;
 139 {
 140   int i;
 141
 142   for (i = 0; i < n_vecs; i++)
 143     sbitmap_ones (bmap[i]);
 144 }
 145
 146 /* Set DST to be A union (B - C).
 147    DST = A | (B & ~C).
 148    Return non-zero if any change is made.  */
 149
 150 int
 151 sbitmap_union_of_diff (dst, a, b, c)
 152      sbitmap dst, a, b, c;
 153 {
 154   int i,changed;
 155   sbitmap_ptr dstp, ap, bp, cp;
 156
 157   changed = 0;
 158   dstp = dst->elms;
 159   ap = a->elms;
 160   bp = b->elms;
 161   cp = c->elms;
 162   for (i = 0; i < dst->size; i++)
 163     {
 164       SBITMAP_ELT_TYPE tmp = *ap | (*bp & ~*cp);
 165       if (*dstp != tmp)
 166         changed = 1;
 167       *dstp = tmp;
 168       dstp++; ap++; bp++; cp++;
 169     }
 170   return changed;
 171 }
 172
 173 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 174
 175 void
 176 sbitmap_not (dst, src)
 177      sbitmap dst, src;
 178 {
 179   int i;
 180   sbitmap_ptr dstp, ap;
 181
 182   dstp = dst->elms;
 183   ap = src->elms;
 184   for (i = 0; i < dst->size; i++)
 185     {
 186       SBITMAP_ELT_TYPE tmp = ~(*ap);
 187       *dstp = tmp;
 188       dstp++; ap++;
 189     }
 190 }
 191
 192 /* Set the bits in DST to be the difference between the bits
 193    in A and the bits in B. i.e. dst = a - b.
 194    The - operator is implemented as a & (~b).  */
 195
 196 void
 197 sbitmap_difference (dst, a, b)
 198      sbitmap dst, a, b;
 199 {
 200   int i;
 201   sbitmap_ptr dstp, ap, bp;
 202
 203   dstp = dst->elms;
 204   ap = a->elms;
 205   bp = b->elms;
 206   for (i = 0; i < dst->size; i++)
 207     *dstp++ = *ap++ & (~*bp++);
 208 }
 209
 210 /* Set DST to be (A and B)).
 211    Return non-zero if any change is made.  */
 212
 213 int
 214 sbitmap_a_and_b (dst, a, b)
 215      sbitmap dst, a, b;
 216 {
 217   int i,changed;
 218   sbitmap_ptr dstp, ap, bp;
 219
 220   changed = 0;
 221   dstp = dst->elms;
 222   ap = a->elms;
 223   bp = b->elms;
 224   for (i = 0; i < dst->size; i++)
 225     {
 226       SBITMAP_ELT_TYPE tmp = *ap & *bp;
 227       if (*dstp != tmp)
 228         changed = 1;
 229       *dstp = tmp;
 230       dstp++; ap++; bp++;
 231     }
 232   return changed;
 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   int i,changed;
 242   sbitmap_ptr dstp, ap, bp;
 243
 244   changed = 0;
 245   dstp = dst->elms;
 246   ap = a->elms;
 247   bp = b->elms;
 248   for (i = 0; i < dst->size; i++)
 249     {
 250       SBITMAP_ELT_TYPE tmp = *ap | *bp;
 251       if (*dstp != tmp)
 252         changed = 1;
 253       *dstp = tmp;
 254       dstp++; ap++; bp++;
 255     }
 256   return changed;
 257 }
 258
 259 /* Set DST to be (A or (B and C)).
 260    Return non-zero if any change is made.  */
 261
 262 int
 263 sbitmap_a_or_b_and_c (dst, a, b, c)
 264      sbitmap dst, a, b, c;
 265 {
 266   int i,changed;
 267   sbitmap_ptr dstp, ap, bp, cp;
 268
 269   changed = 0;
 270   dstp = dst->elms;
 271   ap = a->elms;
 272   bp = b->elms;
 273   cp = c->elms;
 274   for (i = 0; i < dst->size; i++)
 275     {
 276       SBITMAP_ELT_TYPE tmp = *ap | (*bp & *cp);
 277       if (*dstp != tmp)
 278         changed = 1;
 279       *dstp = tmp;
 280       dstp++; ap++; bp++; cp++;
 281     }
 282   return changed;
 283 }
 284
 285 /* Set DST to be (A ann (B or C)).
 286    Return non-zero if any change is made.  */
 287
 288 int
 289 sbitmap_a_and_b_or_c (dst, a, b, c)
 290      sbitmap dst, a, b, c;
 291 {
 292   int i,changed;
 293   sbitmap_ptr dstp, ap, bp, cp;
 294
 295   changed = 0;
 296   dstp = dst->elms;
 297   ap = a->elms;
 298   bp = b->elms;
 299   cp = c->elms;
 300   for (i = 0; i < dst->size; i++)
 301     {
 302       SBITMAP_ELT_TYPE tmp = *ap & (*bp | *cp);
 303       if (*dstp != tmp)
 304         changed = 1;
 305       *dstp = tmp;
 306       dstp++; ap++; bp++; cp++;
 307     }
 308   return changed;
 309 }
 310
 311 /* Set the bitmap DST to the intersection of SRC of all predecessors or
 312    successors of block number BB (PRED_SUCC says which).  */
 313
 314 void
 315 sbitmap_intersect_of_predsucc (dst, src, bb, pred_succ)
 316      sbitmap dst;
 317      sbitmap *src;
 318      int bb;
 319      int_list_ptr *pred_succ;
 320 {
 321   int_list_ptr ps;
 322   int ps_bb;
 323   int set_size = dst->size;
 324
 325   ps = pred_succ[bb];
 326
 327   /* It is possible that there are no predecessors(/successors).
 328      This can happen for example in unreachable code.  */
 329
 330   if (ps == NULL)
 331     {
 332       /* In APL-speak this is the `and' reduction of the empty set and thus
 333          the result is the identity for `and'.  */
 334       sbitmap_ones (dst);
 335       return;
 336     }
 337
 338   /* Set result to first predecessor/successor.  */
 339
 340   for ( ; ps != NULL; ps = ps->next)
 341     {
 342       ps_bb = INT_LIST_VAL (ps);
 343       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 344         continue;
 345       sbitmap_copy (dst, src[ps_bb]);
 346       /* Break out since we're only doing first predecessor.  */
 347       break;
 348     }
 349   if (ps == NULL)
 350     return;
 351
 352   /* Now do the remaining predecessors/successors.  */
 353
 354   for (ps = ps->next; ps != NULL; ps = ps->next)
 355     {
 356       int i;
 357       sbitmap_ptr p,r;
 358
 359       ps_bb = INT_LIST_VAL (ps);
 360       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 361         continue;
 362
 363       p = src[ps_bb]->elms;
 364       r = dst->elms;
 365
 366       for (i = 0; i < set_size; i++)
 367         *r++ &= *p++;
 368     }
 369 }
 370
 371 /* Set the bitmap DST to the union of SRC of all predecessors/successors of
 372    block number BB.  */
 373
 374 void
 375 sbitmap_union_of_predsucc (dst, src, bb, pred_succ)
 376      sbitmap dst;
 377      sbitmap *src;
 378      int bb;
 379      int_list_ptr *pred_succ;
 380 {
 381   int_list_ptr ps;
 382   int ps_bb;
 383   int set_size = dst->size;
 384
 385   ps = pred_succ[bb];
 386
 387   /* It is possible that there are no predecessors(/successors).
 388      This can happen for example in unreachable code.  */
 389
 390   if (ps == NULL)
 391     {
 392       /* In APL-speak this is the `or' reduction of the empty set and thus
 393          the result is the identity for `or'.  */
 394       sbitmap_zero (dst);
 395       return;
 396     }
 397
 398   /* Set result to first predecessor/successor.  */
 399
 400   for ( ; ps != NULL; ps = ps->next)
 401     {
 402       ps_bb = INT_LIST_VAL (ps);
 403       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 404         continue;
 405       sbitmap_copy (dst, src[ps_bb]);
 406       /* Break out since we're only doing first predecessor.  */
 407       break;
 408     }
 409   if (ps == NULL)
 410     return;
 411
 412   /* Now do the remaining predecessors/successors.  */
 413
 414   for (ps = ps->next; ps != NULL; ps = ps->next)
 415     {
 416       int i;
 417       sbitmap_ptr p,r;
 418
 419       ps_bb = INT_LIST_VAL (ps);
 420       if (ps_bb == ENTRY_BLOCK || ps_bb == EXIT_BLOCK)
 421         continue;
 422
 423       p = src[ps_bb]->elms;
 424       r = dst->elms;
 425
 426       for (i = 0; i < set_size; i++)
 427         *r++ |= *p++;
 428     }
 429 }
 430
 431 void
 432 dump_sbitmap (file, bmap)
 433      FILE *file;
 434      sbitmap bmap;
 435 {
 436   int i,j,n;
 437   int set_size = bmap->size;
 438   int total_bits = bmap->n_bits;
 439
 440   fprintf (file, "  ");
 441   for (i = n = 0; i < set_size && n < total_bits; i++)
 442     {
 443       for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 444         {
 445           if (n != 0 && n % 10 == 0)
 446             fprintf (file, " ");
 447           fprintf (file, "%d", (bmap->elms[i] & (1L << j)) != 0);
 448         }
 449     }
 450   fprintf (file, "\n");
 451 }
 452
 453 void
 454 dump_sbitmap_vector (file, title, subtitle, bmaps, n_maps)
 455      FILE *file;
 456      char *title, *subtitle;
 457      sbitmap *bmaps;
 458      int n_maps;
 459 {
 460   int bb;
 461
 462   fprintf (file, "%s\n", title);
 463   for (bb = 0; bb < n_maps; bb++)
 464     {
 465       fprintf (file, "%s %d\n", subtitle, bb);
 466       dump_sbitmap (file, bmaps[bb]);
 467     }
 468   fprintf (file, "\n");
 469 }