gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999-2013 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 /* This suffices for roughly 99% of the hosts we run on, and the rest
  26    don't have 256 bit integers.  */
  27 #if SBITMAP_ELT_BITS > 255
  28 #error Need to increase size of datatype used for popcount
  29 #endif
  30
  31 #if GCC_VERSION >= 3400
  32 #  if SBITMAP_ELT_BITS == HOST_BITS_PER_LONG
  33 #    define do_popcount(x) __builtin_popcountl (x)
  34 #  elif SBITMAP_ELT_BITS == HOST_BITS_PER_LONGLONG
  35 #    define do_popcount(x) __builtin_popcountll (x)
  36 #  else
  37 #    error "internal error: sbitmap.h and hwint.h are inconsistent"
  38 #  endif
  39 #else
  40 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
  41 #  define do_popcount(x) sbitmap_elt_popcount (x)
  42 #endif
  43
  44 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
  45 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
  46
  47 /* Return the size in bytes of a bitmap MAP.  */
  48
  49 static inline unsigned int sbitmap_size_bytes (const_sbitmap map)
  50 {
  51    return map->size * sizeof (SBITMAP_ELT_TYPE);
  52 }
  53
  54 /* This macro controls debugging that is as expensive as the
  55    operations it verifies.  */
  56
  57 /* #define BITMAP_DEBUGGING  */
  58 #ifdef BITMAP_DEBUGGING
  59
  60 /* Verify the population count of sbitmap A matches the cached value,
  61    if there is a cached value. */
  62
  63 static void
  64 sbitmap_verify_popcount (const_sbitmap a)
  65 {
  66   unsigned ix;
  67   unsigned int lastword;
  68
  69   if (!a->popcount)
  70     return;
  71
  72   lastword = a->size;
  73   for (ix = 0; ix < lastword; ix++)
  74     gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
  75 }
  76 #endif
  77
  78 /* Bitmap manipulation routines.  */
  79
  80 /* Allocate a simple bitmap of N_ELMS bits.  */
  81
  82 sbitmap
  83 sbitmap_alloc (unsigned int n_elms)
  84 {
  85   unsigned int bytes, size, amt;
  86   sbitmap bmap;
  87
  88   size = SBITMAP_SET_SIZE (n_elms);
  89   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  90   amt = (sizeof (struct simple_bitmap_def)
  91          + bytes - sizeof (SBITMAP_ELT_TYPE));
  92   bmap = (sbitmap) xmalloc (amt);
  93   bmap->n_bits = n_elms;
  94   bmap->size = size;
  95   bmap->popcount = NULL;
  96   return bmap;
  97 }
  98
  99 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array.  */
 100
 101 sbitmap
 102 sbitmap_alloc_with_popcount (unsigned int n_elms)
 103 {
 104   sbitmap const bmap = sbitmap_alloc (n_elms);
 105   bmap->popcount = XNEWVEC (unsigned char, bmap->size);
 106   return bmap;
 107 }
 108
 109 /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
 110    size of BMAP, clear the new bits to zero if the DEF argument
 111    is zero, and set them to one otherwise.  */
 112
 113 sbitmap
 114 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
 115 {
 116   unsigned int bytes, size, amt;
 117   unsigned int last_bit;
 118
 119   size = SBITMAP_SET_SIZE (n_elms);
 120   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 121   if (bytes > sbitmap_size_bytes (bmap))
 122     {
 123       amt = (sizeof (struct simple_bitmap_def)
 124             + bytes - sizeof (SBITMAP_ELT_TYPE));
 125       bmap = (sbitmap) xrealloc (bmap, amt);
 126       if (bmap->popcount)
 127         bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size);
 128     }
 129
 130   if (n_elms > bmap->n_bits)
 131     {
 132       if (def)
 133         {
 134           memset (bmap->elms + bmap->size, -1,
 135                   bytes - sbitmap_size_bytes (bmap));
 136
 137           /* Set the new bits if the original last element.  */
 138           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 139           if (last_bit)
 140             bmap->elms[bmap->size - 1]
 141               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 142
 143           /* Clear the unused bit in the new last element.  */
 144           last_bit = n_elms % SBITMAP_ELT_BITS;
 145           if (last_bit)
 146             bmap->elms[size - 1]
 147               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 148         }
 149       else
 150         {
 151           memset (bmap->elms + bmap->size, 0,
 152                   bytes - sbitmap_size_bytes (bmap));
 153           if (bmap->popcount)
 154             memset (bmap->popcount + bmap->size, 0,
 155                     (size * sizeof (unsigned char))
 156                     - (bmap->size * sizeof (unsigned char)));
 157
 158         }
 159     }
 160   else if (n_elms < bmap->n_bits)
 161     {
 162       /* Clear the surplus bits in the last word.  */
 163       last_bit = n_elms % SBITMAP_ELT_BITS;
 164       if (last_bit)
 165         {
 166           bmap->elms[size - 1]
 167             &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 168           if (bmap->popcount)
 169             bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
 170         }
 171     }
 172
 173   bmap->n_bits = n_elms;
 174   bmap->size = size;
 175   return bmap;
 176 }
 177
 178 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 179
 180 sbitmap
 181 sbitmap_realloc (sbitmap src, unsigned int n_elms)
 182 {
 183   unsigned int bytes, size, amt;
 184   sbitmap bmap;
 185
 186   size = SBITMAP_SET_SIZE (n_elms);
 187   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 188   amt = (sizeof (struct simple_bitmap_def)
 189          + bytes - sizeof (SBITMAP_ELT_TYPE));
 190
 191   if (sbitmap_size_bytes (src)  >= bytes)
 192     {
 193       src->n_bits = n_elms;
 194       return src;
 195     }
 196
 197   bmap = (sbitmap) xrealloc (src, amt);
 198   bmap->n_bits = n_elms;
 199   bmap->size = size;
 200   return bmap;
 201 }
 202
 203 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 204
 205 sbitmap *
 206 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
 207 {
 208   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
 209   sbitmap *bitmap_vector;
 210
 211   size = SBITMAP_SET_SIZE (n_elms);
 212   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 213   elm_bytes = (sizeof (struct simple_bitmap_def)
 214                + bytes - sizeof (SBITMAP_ELT_TYPE));
 215   vector_bytes = n_vecs * sizeof (sbitmap *);
 216
 217   /* Round up `vector_bytes' to account for the alignment requirements
 218      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
 219      separately, but that requires maintaining two pointers or creating
 220      a cover struct to hold both pointers (so our result is still just
 221      one pointer).  Neither is a bad idea, but this is simpler for now.  */
 222   {
 223     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
 224     struct { char x; SBITMAP_ELT_TYPE y; } align;
 225     int alignment = (char *) & align.y - & align.x;
 226     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
 227   }
 228
 229   amt = vector_bytes + (n_vecs * elm_bytes);
 230   bitmap_vector = (sbitmap *) xmalloc (amt);
 231
 232   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
 233     {
 234       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 235
 236       bitmap_vector[i] = b;
 237       b->n_bits = n_elms;
 238       b->size = size;
 239       b->popcount = NULL;
 240     }
 241
 242   return bitmap_vector;
 243 }
 244
 245 /* Copy sbitmap SRC to DST.  */
 246
 247 void
 248 bitmap_copy (sbitmap dst, const_sbitmap src)
 249 {
 250   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
 251   if (dst->popcount)
 252     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
 253 }
 254
 255 /* Determine if a == b.  */
 256 int
 257 bitmap_equal_p (const_sbitmap a, const_sbitmap b)
 258 {
 259   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
 260 }
 261
 262 /* Return true if the bitmap is empty.  */
 263
 264 bool
 265 bitmap_empty_p (const_sbitmap bmap)
 266 {
 267   unsigned int i;
 268   for (i=0; i<bmap->size; i++)
 269     if (bmap->elms[i])
 270       return false;
 271
 272   return true;
 273 }
 274
 275
 276 /* Zero all elements in a bitmap.  */
 277
 278 void
 279 bitmap_clear (sbitmap bmap)
 280 {
 281   memset (bmap->elms, 0, sbitmap_size_bytes (bmap));
 282   if (bmap->popcount)
 283     memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
 284 }
 285
 286 /* Set all elements in a bitmap to ones.  */
 287
 288 void
 289 bitmap_ones (sbitmap bmap)
 290 {
 291   unsigned int last_bit;
 292
 293   memset (bmap->elms, -1, sbitmap_size_bytes (bmap));
 294   if (bmap->popcount)
 295     memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
 296
 297   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 298   if (last_bit)
 299     {
 300       bmap->elms[bmap->size - 1]
 301         = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 302       if (bmap->popcount)
 303         bmap->popcount[bmap->size - 1]
 304           = do_popcount (bmap->elms[bmap->size - 1]);
 305     }
 306 }
 307
 308 /* Zero a vector of N_VECS bitmaps.  */
 309
 310 void
 311 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs)
 312 {
 313   unsigned int i;
 314
 315   for (i = 0; i < n_vecs; i++)
 316     bitmap_clear (bmap[i]);
 317 }
 318
 319 /* Set a vector of N_VECS bitmaps to ones.  */
 320
 321 void
 322 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 323 {
 324   unsigned int i;
 325
 326   for (i = 0; i < n_vecs; i++)
 327     bitmap_ones (bmap[i]);
 328 }
 329
 330 /* Set DST to be A union (B - C).
 331    DST = A | (B & ~C).
 332    Returns true if any change is made.  */
 333
 334 bool
 335 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 336 {
 337   unsigned int i, n = dst->size;
 338   sbitmap_ptr dstp = dst->elms;
 339   const_sbitmap_ptr ap = a->elms;
 340   const_sbitmap_ptr bp = b->elms;
 341   const_sbitmap_ptr cp = c->elms;
 342   SBITMAP_ELT_TYPE changed = 0;
 343
 344   gcc_assert (!dst->popcount);
 345
 346   for (i = 0; i < n; i++)
 347     {
 348       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 349       changed |= *dstp ^ tmp;
 350       *dstp++ = tmp;
 351     }
 352
 353   return changed != 0;
 354 }
 355
 356 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 357
 358 void
 359 bitmap_not (sbitmap dst, const_sbitmap src)
 360 {
 361   unsigned int i, n = dst->size;
 362   sbitmap_ptr dstp = dst->elms;
 363   const_sbitmap_ptr srcp = src->elms;
 364   unsigned int last_bit;
 365
 366   gcc_assert (!dst->popcount);
 367
 368   for (i = 0; i < n; i++)
 369     *dstp++ = ~*srcp++;
 370
 371   /* Zero all bits past n_bits, by ANDing dst with bitmap_ones.  */
 372   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 373   if (last_bit)
 374     dst->elms[n-1] = dst->elms[n-1]
 375       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 376 }
 377
 378 /* Set the bits in DST to be the difference between the bits
 379    in A and the bits in B. i.e. dst = a & (~b).  */
 380
 381 void
 382 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b)
 383 {
 384   unsigned int i, dst_size = dst->size;
 385   unsigned int min_size = dst->size;
 386   sbitmap_ptr dstp = dst->elms;
 387   const_sbitmap_ptr ap = a->elms;
 388   const_sbitmap_ptr bp = b->elms;
 389
 390   gcc_assert (!dst->popcount);
 391
 392   /* A should be at least as large as DEST, to have a defined source.  */
 393   gcc_assert (a->size >= dst_size);
 394   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 395      only copy the subtrahend into dest.  */
 396   if (b->size < min_size)
 397     min_size = b->size;
 398   for (i = 0; i < min_size; i++)
 399     *dstp++ = *ap++ & (~*bp++);
 400   /* Now fill the rest of dest from A, if B was too short.
 401      This makes sense only when destination and A differ.  */
 402   if (dst != a && i != dst_size)
 403     for (; i < dst_size; i++)
 404       *dstp++ = *ap++;
 405 }
 406
 407 /* Return true if there are any bits set in A are also set in B.
 408    Return false otherwise.  */
 409
 410 bool
 411 bitmap_intersect_p (const_sbitmap a, const_sbitmap b)
 412 {
 413   const_sbitmap_ptr ap = a->elms;
 414   const_sbitmap_ptr bp = b->elms;
 415   unsigned int i, n;
 416
 417   n = MIN (a->size, b->size);
 418   for (i = 0; i < n; i++)
 419     if ((*ap++ & *bp++) != 0)
 420       return true;
 421
 422   return false;
 423 }
 424
 425 /* Set DST to be (A and B).
 426    Return nonzero if any change is made.  */
 427
 428 bool
 429 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b)
 430 {
 431   unsigned int i, n = dst->size;
 432   sbitmap_ptr dstp = dst->elms;
 433   const_sbitmap_ptr ap = a->elms;
 434   const_sbitmap_ptr bp = b->elms;
 435   bool has_popcount = dst->popcount != NULL;
 436   unsigned char *popcountp = dst->popcount;
 437   SBITMAP_ELT_TYPE changed = 0;
 438
 439   for (i = 0; i < n; i++)
 440     {
 441       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 442       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 443       if (has_popcount)
 444         {
 445           if (wordchanged)
 446             *popcountp = do_popcount (tmp);
 447           popcountp++;
 448         }
 449       *dstp++ = tmp;
 450       changed |= wordchanged;
 451     }
 452 #ifdef BITMAP_DEBUGGING
 453   if (has_popcount)
 454     sbitmap_verify_popcount (dst);
 455 #endif
 456   return changed != 0;
 457 }
 458
 459 /* Set DST to be (A xor B)).
 460    Return nonzero if any change is made.  */
 461
 462 bool
 463 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
 464 {
 465   unsigned int i, n = dst->size;
 466   sbitmap_ptr dstp = dst->elms;
 467   const_sbitmap_ptr ap = a->elms;
 468   const_sbitmap_ptr bp = b->elms;
 469   bool has_popcount = dst->popcount != NULL;
 470   unsigned char *popcountp = dst->popcount;
 471   SBITMAP_ELT_TYPE changed = 0;
 472
 473   for (i = 0; i < n; i++)
 474     {
 475       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 476       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 477       if (has_popcount)
 478         {
 479           if (wordchanged)
 480             *popcountp = do_popcount (tmp);
 481           popcountp++;
 482         }
 483       *dstp++ = tmp;
 484       changed |= wordchanged;
 485     }
 486 #ifdef BITMAP_DEBUGGING
 487   if (has_popcount)
 488     sbitmap_verify_popcount (dst);
 489 #endif
 490   return changed != 0;
 491 }
 492
 493 /* Set DST to be (A or B)).
 494    Return nonzero if any change is made.  */
 495
 496 bool
 497 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
 498 {
 499   unsigned int i, n = dst->size;
 500   sbitmap_ptr dstp = dst->elms;
 501   const_sbitmap_ptr ap = a->elms;
 502   const_sbitmap_ptr bp = b->elms;
 503   bool has_popcount = dst->popcount != NULL;
 504   unsigned char *popcountp = dst->popcount;
 505   SBITMAP_ELT_TYPE changed = 0;
 506
 507   for (i = 0; i < n; i++)
 508     {
 509       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 510       SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp;
 511       if (has_popcount)
 512         {
 513           if (wordchanged)
 514             *popcountp = do_popcount (tmp);
 515           popcountp++;
 516         }
 517       *dstp++ = tmp;
 518       changed |= wordchanged;
 519     }
 520 #ifdef BITMAP_DEBUGGING
 521   if (has_popcount)
 522     sbitmap_verify_popcount (dst);
 523 #endif
 524   return changed != 0;
 525 }
 526
 527 /* Return nonzero if A is a subset of B.  */
 528
 529 bool
 530 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
 531 {
 532   unsigned int i, n = a->size;
 533   const_sbitmap_ptr ap, bp;
 534
 535   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 536     if ((*ap | *bp) != *bp)
 537       return false;
 538
 539   return true;
 540 }
 541
 542 /* Set DST to be (A or (B and C)).
 543    Return nonzero if any change is made.  */
 544
 545 bool
 546 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 547 {
 548   unsigned int i, n = dst->size;
 549   sbitmap_ptr dstp = dst->elms;
 550   const_sbitmap_ptr ap = a->elms;
 551   const_sbitmap_ptr bp = b->elms;
 552   const_sbitmap_ptr cp = c->elms;
 553   SBITMAP_ELT_TYPE changed = 0;
 554
 555   gcc_assert (!dst->popcount);
 556
 557   for (i = 0; i < n; i++)
 558     {
 559       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 560       changed |= *dstp ^ tmp;
 561       *dstp++ = tmp;
 562     }
 563
 564   return changed != 0;
 565 }
 566
 567 /* Set DST to be (A and (B or C)).
 568    Return nonzero if any change is made.  */
 569
 570 bool
 571 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 572 {
 573   unsigned int i, n = dst->size;
 574   sbitmap_ptr dstp = dst->elms;
 575   const_sbitmap_ptr ap = a->elms;
 576   const_sbitmap_ptr bp = b->elms;
 577   const_sbitmap_ptr cp = c->elms;
 578   SBITMAP_ELT_TYPE changed = 0;
 579
 580   gcc_assert (!dst->popcount);
 581
 582   for (i = 0; i < n; i++)
 583     {
 584       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 585       changed |= *dstp ^ tmp;
 586       *dstp++ = tmp;
 587     }
 588
 589   return changed != 0;
 590 }
 591
 592 /* Return number of first bit set in the bitmap, -1 if none.  */
 593
 594 int
 595 bitmap_first_set_bit (const_sbitmap bmap)
 596 {
 597   unsigned int n = 0;
 598   sbitmap_iterator sbi;
 599
 600   EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
 601     return n;
 602   return -1;
 603 }
 604
 605 /* Return number of last bit set in the bitmap, -1 if none.  */
 606
 607 int
 608 bitmap_last_set_bit (const_sbitmap bmap)
 609 {
 610   int i;
 611   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 612
 613   for (i = bmap->size - 1; i >= 0; i--)
 614     {
 615       const SBITMAP_ELT_TYPE word = ptr[i];
 616
 617       if (word != 0)
 618         {
 619           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 620           SBITMAP_ELT_TYPE mask
 621             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 622
 623           while (1)
 624             {
 625               if ((word & mask) != 0)
 626                 return index;
 627
 628               mask >>= 1;
 629               index--;
 630             }
 631         }
 632     }
 633
 634   return -1;
 635 }
 636
 637 void
 638 dump_bitmap (FILE *file, const_sbitmap bmap)
 639 {
 640   unsigned int i, n, j;
 641   unsigned int set_size = bmap->size;
 642   unsigned int total_bits = bmap->n_bits;
 643
 644   fprintf (file, "  ");
 645   for (i = n = 0; i < set_size && n < total_bits; i++)
 646     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 647       {
 648         if (n != 0 && n % 10 == 0)
 649           fprintf (file, " ");
 650
 651         fprintf (file, "%d",
 652                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 653       }
 654
 655   fprintf (file, "\n");
 656 }
 657
 658 DEBUG_FUNCTION void
 659 debug_raw (simple_bitmap_def &ref)
 660 {
 661   dump_bitmap (stderr, &ref);
 662 }
 663
 664 DEBUG_FUNCTION void
 665 debug_raw (simple_bitmap_def *ptr)
 666 {
 667   if (ptr)
 668     debug_raw (*ptr);
 669   else
 670     fprintf (stderr, "<nil>\n");
 671 }
 672
 673 void
 674 dump_bitmap_file (FILE *file, const_sbitmap bmap)
 675 {
 676   unsigned int i, pos;
 677
 678   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 679
 680   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 681     if (bitmap_bit_p (bmap, i))
 682       {
 683         if (pos > 70)
 684           {
 685             fprintf (file, "\n  ");
 686             pos = 0;
 687           }
 688
 689         fprintf (file, "%d ", i);
 690         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 691       }
 692
 693   fprintf (file, "}\n");
 694 }
 695
 696 DEBUG_FUNCTION void
 697 debug_bitmap (const_sbitmap bmap)
 698 {
 699   dump_bitmap_file (stderr, bmap);
 700 }
 701
 702 DEBUG_FUNCTION void
 703 debug (simple_bitmap_def &ref)
 704 {
 705   dump_bitmap_file (stderr, &ref);
 706 }
 707
 708 DEBUG_FUNCTION void
 709 debug (simple_bitmap_def *ptr)
 710 {
 711   if (ptr)
 712     debug (*ptr);
 713   else
 714     fprintf (stderr, "<nil>\n");
 715 }
 716
 717 void
 718 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
 719                      sbitmap *bmaps, int n_maps)
 720 {
 721   int i;
 722
 723   fprintf (file, "%s\n", title);
 724   for (i = 0; i < n_maps; i++)
 725     {
 726       fprintf (file, "%s %d\n", subtitle, i);
 727       dump_bitmap (file, bmaps[i]);
 728     }
 729
 730   fprintf (file, "\n");
 731 }
 732
 733 #if GCC_VERSION < 3400
 734 /* Table of number of set bits in a character, indexed by value of char.  */
 735 static const unsigned char popcount_table[] =
 736 {
 737     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
 738     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 739     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 740     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 741     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
 742     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 743     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
 744     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
 745 };
 746
 747 /* Count the bits in an SBITMAP element A.  */
 748
 749 static unsigned long
 750 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
 751 {
 752   unsigned long ret = 0;
 753   unsigned i;
 754
 755   if (a == 0)
 756     return 0;
 757
 758   /* Just do this the table way for now  */
 759   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
 760     ret += popcount_table[(a >> i) & 0xff];
 761   return ret;
 762 }
 763 #endif