gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999-2017 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "sbitmap.h"
  24
  25 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
  26 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
  27
  28 /* Return the size in bytes of a bitmap MAP.  */
  29
  30 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
  31 {
  32    return map->size * sizeof (SBITMAP_ELT_TYPE);
  33 }
  34
  35
  36 /* Bitmap manipulation routines.  */
  37
  38 /* Allocate a simple bitmap of N_ELMS bits.  */
  39
  40 sbitmap
  41 sbitmap_alloc (unsigned int n_elms)
  42 {
  43   unsigned int bytes, size, amt;
  44   sbitmap bmap;
  45
  46   size = SBITMAP_SET_SIZE (n_elms);
  47   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  48   amt = (sizeof (struct simple_bitmap_def)
  49          + bytes - sizeof (SBITMAP_ELT_TYPE));
  50   bmap = (sbitmap) xmalloc (amt);
  51   bmap->n_bits = n_elms;
  52   bmap->size = size;
  53   return bmap;
  54 }
  55
  56 /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
  57    size of BMAP, clear the new bits to zero if the DEF argument
  58    is zero, and set them to one otherwise.  */
  59
  60 sbitmap
  61 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
  62 {
  63   unsigned int bytes, size, amt;
  64   unsigned int last_bit;
  65
  66   size = SBITMAP_SET_SIZE (n_elms);
  67   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  68   if (bytes > sbitmap_size_bytes (bmap))
  69     {
  70       amt = (sizeof (struct simple_bitmap_def)
  71             + bytes - sizeof (SBITMAP_ELT_TYPE));
  72       bmap = (sbitmap) xrealloc (bmap, amt);
  73     }
  74
  75   if (n_elms > bmap->n_bits)
  76     {
  77       if (def)
  78         {
  79           memset (bmap->elms + bmap->size, -1,
  80                   bytes - sbitmap_size_bytes (bmap));
  81
  82           /* Set the new bits if the original last element.  */
  83           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
  84           if (last_bit)
  85             bmap->elms[bmap->size - 1]
  86               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
  87
  88           /* Clear the unused bit in the new last element.  */
  89           last_bit = n_elms % SBITMAP_ELT_BITS;
  90           if (last_bit)
  91             bmap->elms[size - 1]
  92               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
  93         }
  94       else
  95         memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap));
  96     }
  97   else if (n_elms < bmap->n_bits)
  98     {
  99       /* Clear the surplus bits in the last word.  */
 100       last_bit = n_elms % SBITMAP_ELT_BITS;
 101       if (last_bit)
 102         bmap->elms[size - 1]
 103           &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 104     }
 105
 106   bmap->n_bits = n_elms;
 107   bmap->size = size;
 108   return bmap;
 109 }
 110
 111 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 112
 113 sbitmap
 114 sbitmap_realloc (sbitmap src, unsigned int n_elms)
 115 {
 116   unsigned int bytes, size, amt;
 117   sbitmap bmap;
 118
 119   size = SBITMAP_SET_SIZE (n_elms);
 120   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 121   amt = (sizeof (struct simple_bitmap_def)
 122          + bytes - sizeof (SBITMAP_ELT_TYPE));
 123
 124   if (sbitmap_size_bytes (src)  >= bytes)
 125     {
 126       src->n_bits = n_elms;
 127       return src;
 128     }
 129
 130   bmap = (sbitmap) xrealloc (src, amt);
 131   bmap->n_bits = n_elms;
 132   bmap->size = size;
 133   return bmap;
 134 }
 135
 136 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 137
 138 sbitmap *
 139 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
 140 {
 141   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
 142   sbitmap *bitmap_vector;
 143
 144   size = SBITMAP_SET_SIZE (n_elms);
 145   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 146   elm_bytes = (sizeof (struct simple_bitmap_def)
 147                + bytes - sizeof (SBITMAP_ELT_TYPE));
 148   vector_bytes = n_vecs * sizeof (sbitmap *);
 149
 150   /* Round up `vector_bytes' to account for the alignment requirements
 151      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
 152      separately, but that requires maintaining two pointers or creating
 153      a cover struct to hold both pointers (so our result is still just
 154      one pointer).  Neither is a bad idea, but this is simpler for now.  */
 155   {
 156     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
 157     struct { char x; SBITMAP_ELT_TYPE y; } align;
 158     int alignment = (char *) & align.y - & align.x;
 159     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
 160   }
 161
 162   amt = vector_bytes + (n_vecs * elm_bytes);
 163   bitmap_vector = (sbitmap *) xmalloc (amt);
 164
 165   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
 166     {
 167       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 168
 169       bitmap_vector[i] = b;
 170       b->n_bits = n_elms;
 171       b->size = size;
 172     }
 173
 174   return bitmap_vector;
 175 }
 176
 177 /* Copy sbitmap SRC to DST.  */
 178
 179 void
 180 bitmap_copy (sbitmap dst, const_sbitmap src)
 181 {
 182   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
 183 }
 184
 185 /* Determine if a == b.  */
 186 int
 187 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
 188 {
 189   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
 190 }
 191
 192 /* Return true if the bitmap is empty.  */
 193
 194 bool
 195 bitmap_empty_p (const_sbitmap bmap)
 196 {
 197   unsigned int i;
 198   for (i=0; i<bmap->size; i++)
 199     if (bmap->elms[i])
 200       return false;
 201
 202   return true;
 203 }
 204
 205
 206 /* Zero all elements in a bitmap.  */
 207
 208 void
 209 bitmap_clear (sbitmap bmap)
 210 {
 211   memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
 212 }
 213
 214 /* Set all elements in a bitmap to ones.  */
 215
 216 void
 217 bitmap_ones (sbitmap bmap)
 218 {
 219   unsigned int last_bit;
 220
 221   memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
 222
 223   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 224   if (last_bit)
 225     bmap->elms[bmap->size - 1]
 226       = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 227 }
 228
 229 /* Zero a vector of N_VECS bitmaps.  */
 230
 231 void
 232 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
 233 {
 234   unsigned int i;
 235
 236   for (i = 0; i < n_vecs; i++)
 237     bitmap_clear (bmap[i]);
 238 }
 239
 240 /* Set a vector of N_VECS bitmaps to ones.  */
 241
 242 void
 243 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 244 {
 245   unsigned int i;
 246
 247   for (i = 0; i < n_vecs; i++)
 248     bitmap_ones (bmap[i]);
 249 }
 250
 251 /* Set DST to be A union (B - C).
 252    DST = A | (B & ~C).
 253    Returns true if any change is made.  */
 254
 255 bool
 256 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 257 {
 258   unsigned int i, n = dst->size;
 259   sbitmap_ptr dstp = dst->elms;
 260   const_sbitmap_ptr ap = a->elms;
 261   const_sbitmap_ptr bp = b->elms;
 262   const_sbitmap_ptr cp = c->elms;
 263   SBITMAP_ELT_TYPE changed = 0;
 264
 265   for (i = 0; i < n; i++)
 266     {
 267       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 268       changed |= *dstp ^ tmp;
 269       *dstp++ = tmp;
 270     }
 271
 272   return changed != 0;
 273 }
 274
 275 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 276
 277 void
 278 bitmap_not (sbitmap dst, const_sbitmap src)
 279 {
 280   unsigned int i, n = dst->size;
 281   sbitmap_ptr dstp = dst->elms;
 282   const_sbitmap_ptr srcp = src->elms;
 283   unsigned int last_bit;
 284
 285   for (i = 0; i < n; i++)
 286     *dstp++ = ~*srcp++;
 287
 288   /* Zero all bits past n_bits, by ANDing dst with bitmap_ones.  */
 289   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 290   if (last_bit)
 291     dst->elms[n-1] = dst->elms[n-1]
 292       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 293 }
 294
 295 /* Set the bits in DST to be the difference between the bits
 296    in A and the bits in B. i.e. dst = a & (~b).  */
 297
 298 void
 299 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
 300 {
 301   unsigned int i, dst_size = dst->size;
 302   unsigned int min_size = dst->size;
 303   sbitmap_ptr dstp = dst->elms;
 304   const_sbitmap_ptr ap = a->elms;
 305   const_sbitmap_ptr bp = b->elms;
 306
 307   /* A should be at least as large as DEST, to have a defined source.  */
 308   gcc_assert (a->size >= dst_size);
 309   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 310      only copy the subtrahend into dest.  */
 311   if (b->size < min_size)
 312     min_size = b->size;
 313   for (i = 0; i < min_size; i++)
 314     *dstp++ = *ap++ & (~*bp++);
 315   /* Now fill the rest of dest from A, if B was too short.
 316      This makes sense only when destination and A differ.  */
 317   if (dst != a && i != dst_size)
 318     for (; i < dst_size; i++)
 319       *dstp++ = *ap++;
 320 }
 321
 322 /* Return true if there are any bits set in A are also set in B.
 323    Return false otherwise.  */
 324
 325 bool
 326 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
 327 {
 328   const_sbitmap_ptr ap = a->elms;
 329   const_sbitmap_ptr bp = b->elms;
 330   unsigned int i, n;
 331
 332   n = MIN (a->size, b->size);
 333   for (i = 0; i < n; i++)
 334     if ((*ap++ & *bp++) != 0)
 335       return true;
 336
 337   return false;
 338 }
 339
 340 /* Set DST to be (A and B).
 341    Return nonzero if any change is made.  */
 342
 343 bool
 344 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
 345 {
 346   unsigned int i, n = dst->size;
 347   sbitmap_ptr dstp = dst->elms;
 348   const_sbitmap_ptr ap = a->elms;
 349   const_sbitmap_ptr bp = b->elms;
 350   SBITMAP_ELT_TYPE changed = 0;
 351
 352   for (i = 0; i < n; i++)
 353     {
 354       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 355       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 356       *dstp++ = tmp;
 357       changed |= wordchanged;
 358     }
 359   return changed != 0;
 360 }
 361
 362 /* Set DST to be (A xor B)).
 363    Return nonzero if any change is made.  */
 364
 365 bool
 366 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
 367 {
 368   unsigned int i, n = dst->size;
 369   sbitmap_ptr dstp = dst->elms;
 370   const_sbitmap_ptr ap = a->elms;
 371   const_sbitmap_ptr bp = b->elms;
 372   SBITMAP_ELT_TYPE changed = 0;
 373
 374   for (i = 0; i < n; i++)
 375     {
 376       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 377       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 378       *dstp++ = tmp;
 379       changed |= wordchanged;
 380     }
 381   return changed != 0;
 382 }
 383
 384 /* Set DST to be (A or B)).
 385    Return nonzero if any change is made.  */
 386
 387 bool
 388 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
 389 {
 390   unsigned int i, n = dst->size;
 391   sbitmap_ptr dstp = dst->elms;
 392   const_sbitmap_ptr ap = a->elms;
 393   const_sbitmap_ptr bp = b->elms;
 394   SBITMAP_ELT_TYPE changed = 0;
 395
 396   for (i = 0; i < n; i++)
 397     {
 398       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 399       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 400       *dstp++ = tmp;
 401       changed |= wordchanged;
 402     }
 403   return changed != 0;
 404 }
 405
 406 /* Return nonzero if A is a subset of B.  */
 407
 408 bool
 409 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
 410 {
 411   unsigned int i, n = a->size;
 412   const_sbitmap_ptr ap, bp;
 413
 414   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 415     if ((*ap | *bp) != *bp)
 416       return false;
 417
 418   return true;
 419 }
 420
 421 /* Set DST to be (A or (B and C)).
 422    Return nonzero if any change is made.  */
 423
 424 bool
 425 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 426 {
 427   unsigned int i, n = dst->size;
 428   sbitmap_ptr dstp = dst->elms;
 429   const_sbitmap_ptr ap = a->elms;
 430   const_sbitmap_ptr bp = b->elms;
 431   const_sbitmap_ptr cp = c->elms;
 432   SBITMAP_ELT_TYPE changed = 0;
 433
 434   for (i = 0; i < n; i++)
 435     {
 436       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 437       changed |= *dstp ^ tmp;
 438       *dstp++ = tmp;
 439     }
 440
 441   return changed != 0;
 442 }
 443
 444 /* Set DST to be (A and (B or C)).
 445    Return nonzero if any change is made.  */
 446
 447 bool
 448 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 449 {
 450   unsigned int i, n = dst->size;
 451   sbitmap_ptr dstp = dst->elms;
 452   const_sbitmap_ptr ap = a->elms;
 453   const_sbitmap_ptr bp = b->elms;
 454   const_sbitmap_ptr cp = c->elms;
 455   SBITMAP_ELT_TYPE changed = 0;
 456
 457   for (i = 0; i < n; i++)
 458     {
 459       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 460       changed |= *dstp ^ tmp;
 461       *dstp++ = tmp;
 462     }
 463
 464   return changed != 0;
 465 }
 466
 467 /* Return number of first bit set in the bitmap, -1 if none.  */
 468
 469 int
 470 bitmap_first_set_bit (const_sbitmap bmap)
 471 {
 472   unsigned int n = 0;
 473   sbitmap_iterator sbi;
 474
 475   EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
 476     return n;
 477   return -1;
 478 }
 479
 480 /* Return number of last bit set in the bitmap, -1 if none.  */
 481
 482 int
 483 bitmap_last_set_bit (const_sbitmap bmap)
 484 {
 485   int i;
 486   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 487
 488   for (i = bmap->size - 1; i >= 0; i--)
 489     {
 490       const SBITMAP_ELT_TYPE word = ptr[i];
 491
 492       if (word != 0)
 493         {
 494           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 495           SBITMAP_ELT_TYPE mask
 496             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 497
 498           while (1)
 499             {
 500               if ((word & mask) != 0)
 501                 return index;
 502
 503               mask >>= 1;
 504               index--;
 505             }
 506         }
 507     }
 508
 509   return -1;
 510 }
 511
 512 void
 513 dump_bitmap (FILE *file, const_sbitmap bmap)
 514 {
 515   unsigned int i, n, j;
 516   unsigned int set_size = bmap->size;
 517   unsigned int total_bits = bmap->n_bits;
 518
 519   fprintf (file, "  ");
 520   for (i = n = 0; i < set_size && n < total_bits; i++)
 521     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 522       {
 523         if (n != 0 && n % 10 == 0)
 524           fprintf (file, " ");
 525
 526         fprintf (file, "%d",
 527                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 528       }
 529
 530   fprintf (file, "\n");
 531 }
 532
 533 DEBUG_FUNCTION void
 534 debug_raw (simple_bitmap_def &ref)
 535 {
 536   dump_bitmap (stderr, &ref);
 537 }
 538
 539 DEBUG_FUNCTION void
 540 debug_raw (simple_bitmap_def *ptr)
 541 {
 542   if (ptr)
 543     debug_raw (*ptr);
 544   else
 545     fprintf (stderr, "<nil>\n");
 546 }
 547
 548 void
 549 dump_bitmap_file (FILE *file, const_sbitmap bmap)
 550 {
 551   unsigned int i, pos;
 552
 553   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 554
 555   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 556     if (bitmap_bit_p (bmap, i))
 557       {
 558         if (pos > 70)
 559           {
 560             fprintf (file, "\n  ");
 561             pos = 0;
 562           }
 563
 564         fprintf (file, "%d ", i);
 565         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 566       }
 567
 568   fprintf (file, "}\n");
 569 }
 570
 571 DEBUG_FUNCTION void
 572 debug_bitmap (const_sbitmap bmap)
 573 {
 574   dump_bitmap_file (stderr, bmap);
 575 }
 576
 577 DEBUG_FUNCTION void
 578 debug (simple_bitmap_def &ref)
 579 {
 580   dump_bitmap_file (stderr, &ref);
 581 }
 582
 583 DEBUG_FUNCTION void
 584 debug (simple_bitmap_def *ptr)
 585 {
 586   if (ptr)
 587     debug (*ptr);
 588   else
 589     fprintf (stderr, "<nil>\n");
 590 }
 591
 592 void
 593 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
 594                      sbitmap *bmaps, int n_maps)
 595 {
 596   int i;
 597
 598   fprintf (file, "%s\n", title);
 599   for (i = 0; i < n_maps; i++)
 600     {
 601       fprintf (file, "%s %d\n", subtitle, i);
 602       dump_bitmap (file, bmaps[i]);
 603     }
 604
 605   fprintf (file, "\n");
 606 }