gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999-2012  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   bool anychange = false;
 438
 439   for (i = 0; i < n; i++)
 440     {
 441       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 442       if (has_popcount)
 443         {
 444           bool wordchanged = (*dstp ^ tmp) != 0;
 445           if (wordchanged)
 446             {
 447               *popcountp = do_popcount (tmp);
 448               anychange = true;
 449             }
 450           popcountp++;
 451         }
 452       *dstp++ = tmp;
 453     }
 454 #ifdef BITMAP_DEBUGGING
 455   if (has_popcount)
 456     sbitmap_verify_popcount (dst);
 457 #endif
 458   return anychange;
 459 }
 460
 461 /* Set DST to be (A xor B)).
 462    Return nonzero if any change is made.  */
 463
 464 bool
 465 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b)
 466 {
 467   unsigned int i, n = dst->size;
 468   sbitmap_ptr dstp = dst->elms;
 469   const_sbitmap_ptr ap = a->elms;
 470   const_sbitmap_ptr bp = b->elms;
 471   bool has_popcount = dst->popcount != NULL;
 472   unsigned char *popcountp = dst->popcount;
 473   bool anychange = false;
 474
 475   for (i = 0; i < n; i++)
 476     {
 477       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 478       if (has_popcount)
 479         {
 480           bool wordchanged = (*dstp ^ tmp) != 0;
 481           if (wordchanged)
 482             {
 483               *popcountp = do_popcount (tmp);
 484               anychange = true;
 485             }
 486           popcountp++;
 487         }
 488       *dstp++ = tmp;
 489     }
 490 #ifdef BITMAP_DEBUGGING
 491   if (has_popcount)
 492     sbitmap_verify_popcount (dst);
 493 #endif
 494   return anychange;
 495 }
 496
 497 /* Set DST to be (A or B)).
 498    Return nonzero if any change is made.  */
 499
 500 bool
 501 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b)
 502 {
 503   unsigned int i, n = dst->size;
 504   sbitmap_ptr dstp = dst->elms;
 505   const_sbitmap_ptr ap = a->elms;
 506   const_sbitmap_ptr bp = b->elms;
 507   bool has_popcount = dst->popcount != NULL;
 508   unsigned char *popcountp = dst->popcount;
 509   bool anychange = false;
 510
 511   for (i = 0; i < n; i++)
 512     {
 513       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 514       if (has_popcount)
 515         {
 516           bool wordchanged = (*dstp ^ tmp) != 0;
 517           if (wordchanged)
 518             {
 519               *popcountp = do_popcount (tmp);
 520               anychange = true;
 521             }
 522           popcountp++;
 523         }
 524       *dstp++ = tmp;
 525     }
 526 #ifdef BITMAP_DEBUGGING
 527   if (has_popcount)
 528     sbitmap_verify_popcount (dst);
 529 #endif
 530   return anychange;
 531 }
 532
 533 /* Return nonzero if A is a subset of B.  */
 534
 535 bool
 536 bitmap_subset_p (const_sbitmap a, const_sbitmap b)
 537 {
 538   unsigned int i, n = a->size;
 539   const_sbitmap_ptr ap, bp;
 540
 541   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 542     if ((*ap | *bp) != *bp)
 543       return false;
 544
 545   return true;
 546 }
 547
 548 /* Set DST to be (A or (B and C)).
 549    Return nonzero if any change is made.  */
 550
 551 bool
 552 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 553 {
 554   unsigned int i, n = dst->size;
 555   sbitmap_ptr dstp = dst->elms;
 556   const_sbitmap_ptr ap = a->elms;
 557   const_sbitmap_ptr bp = b->elms;
 558   const_sbitmap_ptr cp = c->elms;
 559   SBITMAP_ELT_TYPE changed = 0;
 560
 561   gcc_assert (!dst->popcount);
 562
 563   for (i = 0; i < n; i++)
 564     {
 565       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 566       changed |= *dstp ^ tmp;
 567       *dstp++ = tmp;
 568     }
 569
 570   return changed != 0;
 571 }
 572
 573 /* Set DST to be (A and (B or C)).
 574    Return nonzero if any change is made.  */
 575
 576 bool
 577 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 578 {
 579   unsigned int i, n = dst->size;
 580   sbitmap_ptr dstp = dst->elms;
 581   const_sbitmap_ptr ap = a->elms;
 582   const_sbitmap_ptr bp = b->elms;
 583   const_sbitmap_ptr cp = c->elms;
 584   SBITMAP_ELT_TYPE changed = 0;
 585
 586   gcc_assert (!dst->popcount);
 587
 588   for (i = 0; i < n; i++)
 589     {
 590       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 591       changed |= *dstp ^ tmp;
 592       *dstp++ = tmp;
 593     }
 594
 595   return changed != 0;
 596 }
 597
 598 /* Return number of first bit set in the bitmap, -1 if none.  */
 599
 600 int
 601 bitmap_first_set_bit (const_sbitmap bmap)
 602 {
 603   unsigned int n = 0;
 604   sbitmap_iterator sbi;
 605
 606   EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi)
 607     return n;
 608   return -1;
 609 }
 610
 611 /* Return number of last bit set in the bitmap, -1 if none.  */
 612
 613 int
 614 bitmap_last_set_bit (const_sbitmap bmap)
 615 {
 616   int i;
 617   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 618
 619   for (i = bmap->size - 1; i >= 0; i--)
 620     {
 621       const SBITMAP_ELT_TYPE word = ptr[i];
 622
 623       if (word != 0)
 624         {
 625           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 626           SBITMAP_ELT_TYPE mask
 627             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 628
 629           while (1)
 630             {
 631               if ((word & mask) != 0)
 632                 return index;
 633
 634               mask >>= 1;
 635               index--;
 636             }
 637         }
 638     }
 639
 640   return -1;
 641 }
 642
 643 void
 644 dump_bitmap (FILE *file, const_sbitmap bmap)
 645 {
 646   unsigned int i, n, j;
 647   unsigned int set_size = bmap->size;
 648   unsigned int total_bits = bmap->n_bits;
 649
 650   fprintf (file, "  ");
 651   for (i = n = 0; i < set_size && n < total_bits; i++)
 652     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 653       {
 654         if (n != 0 && n % 10 == 0)
 655           fprintf (file, " ");
 656
 657         fprintf (file, "%d",
 658                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 659       }
 660
 661   fprintf (file, "\n");
 662 }
 663
 664 void
 665 dump_bitmap_file (FILE *file, const_sbitmap bmap)
 666 {
 667   unsigned int i, pos;
 668
 669   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 670
 671   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 672     if (bitmap_bit_p (bmap, i))
 673       {
 674         if (pos > 70)
 675           {
 676             fprintf (file, "\n  ");
 677             pos = 0;
 678           }
 679
 680         fprintf (file, "%d ", i);
 681         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 682       }
 683
 684   fprintf (file, "}\n");
 685 }
 686
 687 DEBUG_FUNCTION void
 688 debug_bitmap (const_sbitmap bmap)
 689 {
 690   dump_bitmap_file (stderr, bmap);
 691 }
 692
 693 void
 694 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle,
 695                      sbitmap *bmaps, int n_maps)
 696 {
 697   int i;
 698
 699   fprintf (file, "%s\n", title);
 700   for (i = 0; i < n_maps; i++)
 701     {
 702       fprintf (file, "%s %d\n", subtitle, i);
 703       dump_bitmap (file, bmaps[i]);
 704     }
 705
 706   fprintf (file, "\n");
 707 }
 708
 709 #if GCC_VERSION < 3400
 710 /* Table of number of set bits in a character, indexed by value of char.  */
 711 static const unsigned char popcount_table[] =
 712 {
 713     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,
 714     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,
 715     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,
 716     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,
 717     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,
 718     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,
 719     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,
 720     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,
 721 };
 722
 723 /* Count the bits in an SBITMAP element A.  */
 724
 725 static unsigned long
 726 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
 727 {
 728   unsigned long ret = 0;
 729   unsigned i;
 730
 731   if (a == 0)
 732     return 0;
 733
 734   /* Just do this the table way for now  */
 735   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
 736     ret += popcount_table[(a >> i) & 0xff];
 737   return ret;
 738 }
 739 #endif