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