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 sbitmap_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 sbitmap_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 sbitmap_equal (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 sbitmap_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 sbitmap_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 sbitmap_zero (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 sbitmap_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 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
 365 {
 366   unsigned int i;
 367
 368   for (i = 0; i < n_vecs; i++)
 369     sbitmap_zero (bmap[i]);
 370 }
 371
 372 /* Set a vector of N_VECS bitmaps to ones.  */
 373
 374 void
 375 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 376 {
 377   unsigned int i;
 378
 379   for (i = 0; i < n_vecs; i++)
 380     sbitmap_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 sbitmap_union_of_diff_cg (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 void
 410 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 411 {
 412   unsigned int i, n = dst->size;
 413   sbitmap_ptr dstp = dst->elms;
 414   const_sbitmap_ptr ap = a->elms;
 415   const_sbitmap_ptr bp = b->elms;
 416   const_sbitmap_ptr cp = c->elms;
 417
 418   gcc_assert (!dst->popcount && !a->popcount
 419               && !b->popcount && !c->popcount);
 420
 421   for (i = 0; i < n; i++)
 422     *dstp++ = *ap++ | (*bp++ & ~*cp++);
 423 }
 424
 425 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 426
 427 void
 428 sbitmap_not (sbitmap dst, const_sbitmap src)
 429 {
 430   unsigned int i, n = dst->size;
 431   sbitmap_ptr dstp = dst->elms;
 432   const_sbitmap_ptr srcp = src->elms;
 433   unsigned int last_bit;
 434
 435   gcc_assert (!dst->popcount);
 436
 437   for (i = 0; i < n; i++)
 438     *dstp++ = ~*srcp++;
 439
 440   /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
 441   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 442   if (last_bit)
 443     dst->elms[n-1] = dst->elms[n-1]
 444       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 445 }
 446
 447 /* Set the bits in DST to be the difference between the bits
 448    in A and the bits in B. i.e. dst = a & (~b).  */
 449
 450 void
 451 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
 452 {
 453   unsigned int i, dst_size = dst->size;
 454   unsigned int min_size = dst->size;
 455   sbitmap_ptr dstp = dst->elms;
 456   const_sbitmap_ptr ap = a->elms;
 457   const_sbitmap_ptr bp = b->elms;
 458
 459   gcc_assert (!dst->popcount);
 460
 461   /* A should be at least as large as DEST, to have a defined source.  */
 462   gcc_assert (a->size >= dst_size);
 463   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 464      only copy the subtrahend into dest.  */
 465   if (b->size < min_size)
 466     min_size = b->size;
 467   for (i = 0; i < min_size; i++)
 468     *dstp++ = *ap++ & (~*bp++);
 469   /* Now fill the rest of dest from A, if B was too short.
 470      This makes sense only when destination and A differ.  */
 471   if (dst != a && i != dst_size)
 472     for (; i < dst_size; i++)
 473       *dstp++ = *ap++;
 474 }
 475
 476 /* Return true if there are any bits set in A are also set in B.
 477    Return false otherwise.  */
 478
 479 bool
 480 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
 481 {
 482   const_sbitmap_ptr ap = a->elms;
 483   const_sbitmap_ptr bp = b->elms;
 484   unsigned int i, n;
 485
 486   n = MIN (a->size, b->size);
 487   for (i = 0; i < n; i++)
 488     if ((*ap++ & *bp++) != 0)
 489       return true;
 490
 491   return false;
 492 }
 493
 494 /* Set DST to be (A and B).
 495    Return nonzero if any change is made.  */
 496
 497 bool
 498 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 499 {
 500   unsigned int i, n = dst->size;
 501   sbitmap_ptr dstp = dst->elms;
 502   const_sbitmap_ptr ap = a->elms;
 503   const_sbitmap_ptr bp = b->elms;
 504   SBITMAP_ELT_TYPE changed = 0;
 505
 506   gcc_assert (!dst->popcount);
 507
 508   for (i = 0; i < n; i++)
 509     {
 510       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 511       changed |= *dstp ^ tmp;
 512       *dstp++ = tmp;
 513     }
 514
 515   return changed != 0;
 516 }
 517
 518 void
 519 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 520 {
 521   unsigned int i, n = dst->size;
 522   sbitmap_ptr dstp = dst->elms;
 523   const_sbitmap_ptr ap = a->elms;
 524   const_sbitmap_ptr bp = b->elms;
 525   bool has_popcount = dst->popcount != NULL;
 526   unsigned char *popcountp = dst->popcount;
 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             *popcountp = do_popcount (tmp);
 536           popcountp++;
 537         }
 538       *dstp++ = tmp;
 539     }
 540 #ifdef BITMAP_DEBUGGING
 541   if (has_popcount)
 542     sbitmap_verify_popcount (dst);
 543 #endif
 544 }
 545
 546 /* Set DST to be (A xor B)).
 547    Return nonzero if any change is made.  */
 548
 549 bool
 550 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 551 {
 552   unsigned int i, n = dst->size;
 553   sbitmap_ptr dstp = dst->elms;
 554   const_sbitmap_ptr ap = a->elms;
 555   const_sbitmap_ptr bp = b->elms;
 556   SBITMAP_ELT_TYPE changed = 0;
 557
 558   gcc_assert (!dst->popcount);
 559
 560   for (i = 0; i < n; i++)
 561     {
 562       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 563       changed |= *dstp ^ tmp;
 564       *dstp++ = tmp;
 565     }
 566
 567   return changed != 0;
 568 }
 569
 570 void
 571 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 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   bool has_popcount = dst->popcount != NULL;
 578   unsigned char *popcountp = dst->popcount;
 579
 580   for (i = 0; i < n; i++)
 581     {
 582       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 583       if (has_popcount)
 584         {
 585           bool wordchanged = (*dstp ^ tmp) != 0;
 586           if (wordchanged)
 587             *popcountp = do_popcount (tmp);
 588           popcountp++;
 589         }
 590       *dstp++ = tmp;
 591     }
 592 #ifdef BITMAP_DEBUGGING
 593   if (has_popcount)
 594     sbitmap_verify_popcount (dst);
 595 #endif
 596 }
 597
 598 /* Set DST to be (A or B)).
 599    Return nonzero if any change is made.  */
 600
 601 bool
 602 sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 603 {
 604   unsigned int i, n = dst->size;
 605   sbitmap_ptr dstp = dst->elms;
 606   const_sbitmap_ptr ap = a->elms;
 607   const_sbitmap_ptr bp = b->elms;
 608   SBITMAP_ELT_TYPE changed = 0;
 609
 610   gcc_assert (!dst->popcount);
 611
 612   for (i = 0; i < n; i++)
 613     {
 614       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 615       changed |= *dstp ^ tmp;
 616       *dstp++ = tmp;
 617     }
 618
 619   return changed != 0;
 620 }
 621
 622 void
 623 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 624 {
 625   unsigned int i, n = dst->size;
 626   sbitmap_ptr dstp = dst->elms;
 627   const_sbitmap_ptr ap = a->elms;
 628   const_sbitmap_ptr bp = b->elms;
 629   bool has_popcount = dst->popcount != NULL;
 630   unsigned char *popcountp = dst->popcount;
 631
 632   for (i = 0; i < n; i++)
 633     {
 634       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 635       if (has_popcount)
 636         {
 637           bool wordchanged = (*dstp ^ tmp) != 0;
 638           if (wordchanged)
 639             *popcountp = do_popcount (tmp);
 640           popcountp++;
 641         }
 642       *dstp++ = tmp;
 643     }
 644 #ifdef BITMAP_DEBUGGING
 645   if (has_popcount)
 646     sbitmap_verify_popcount (dst);
 647 #endif
 648 }
 649
 650 /* Return nonzero if A is a subset of B.  */
 651
 652 bool
 653 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
 654 {
 655   unsigned int i, n = a->size;
 656   const_sbitmap_ptr ap, bp;
 657
 658   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 659     if ((*ap | *bp) != *bp)
 660       return false;
 661
 662   return true;
 663 }
 664
 665 /* Set DST to be (A or (B and C)).
 666    Return nonzero if any change is made.  */
 667
 668 bool
 669 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 670 {
 671   unsigned int i, n = dst->size;
 672   sbitmap_ptr dstp = dst->elms;
 673   const_sbitmap_ptr ap = a->elms;
 674   const_sbitmap_ptr bp = b->elms;
 675   const_sbitmap_ptr cp = c->elms;
 676   SBITMAP_ELT_TYPE changed = 0;
 677
 678   gcc_assert (!dst->popcount);
 679
 680   for (i = 0; i < n; i++)
 681     {
 682       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 683       changed |= *dstp ^ tmp;
 684       *dstp++ = tmp;
 685     }
 686
 687   return changed != 0;
 688 }
 689
 690 void
 691 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 692 {
 693   unsigned int i, n = dst->size;
 694   sbitmap_ptr dstp = dst->elms;
 695   const_sbitmap_ptr ap = a->elms;
 696   const_sbitmap_ptr bp = b->elms;
 697   const_sbitmap_ptr cp = c->elms;
 698
 699   gcc_assert (!dst->popcount);
 700
 701   for (i = 0; i < n; i++)
 702     *dstp++ = *ap++ | (*bp++ & *cp++);
 703 }
 704
 705 /* Set DST to be (A and (B or C)).
 706    Return nonzero if any change is made.  */
 707
 708 bool
 709 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 710 {
 711   unsigned int i, n = dst->size;
 712   sbitmap_ptr dstp = dst->elms;
 713   const_sbitmap_ptr ap = a->elms;
 714   const_sbitmap_ptr bp = b->elms;
 715   const_sbitmap_ptr cp = c->elms;
 716   SBITMAP_ELT_TYPE changed = 0;
 717
 718   gcc_assert (!dst->popcount);
 719
 720   for (i = 0; i < n; i++)
 721     {
 722       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 723       changed |= *dstp ^ tmp;
 724       *dstp++ = tmp;
 725     }
 726
 727   return changed != 0;
 728 }
 729
 730 void
 731 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 732 {
 733   unsigned int i, n = dst->size;
 734   sbitmap_ptr dstp = dst->elms;
 735   const_sbitmap_ptr ap = a->elms;
 736   const_sbitmap_ptr bp = b->elms;
 737   const_sbitmap_ptr cp = c->elms;
 738
 739   for (i = 0; i < n; i++)
 740     *dstp++ = *ap++ & (*bp++ | *cp++);
 741 }
 742
 743 /* Return number of first bit set in the bitmap, -1 if none.  */
 744
 745 int
 746 sbitmap_first_set_bit (const_sbitmap bmap)
 747 {
 748   unsigned int n = 0;
 749   sbitmap_iterator sbi;
 750
 751   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
 752     return n;
 753   return -1;
 754 }
 755
 756 /* Return number of last bit set in the bitmap, -1 if none.  */
 757
 758 int
 759 sbitmap_last_set_bit (const_sbitmap bmap)
 760 {
 761   int i;
 762   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 763
 764   for (i = bmap->size - 1; i >= 0; i--)
 765     {
 766       const SBITMAP_ELT_TYPE word = ptr[i];
 767
 768       if (word != 0)
 769         {
 770           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 771           SBITMAP_ELT_TYPE mask
 772             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 773
 774           while (1)
 775             {
 776               if ((word & mask) != 0)
 777                 return index;
 778
 779               mask >>= 1;
 780               index--;
 781             }
 782         }
 783     }
 784
 785   return -1;
 786 }
 787
 788 void
 789 dump_sbitmap (FILE *file, const_sbitmap bmap)
 790 {
 791   unsigned int i, n, j;
 792   unsigned int set_size = bmap->size;
 793   unsigned int total_bits = bmap->n_bits;
 794
 795   fprintf (file, "  ");
 796   for (i = n = 0; i < set_size && n < total_bits; i++)
 797     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 798       {
 799         if (n != 0 && n % 10 == 0)
 800           fprintf (file, " ");
 801
 802         fprintf (file, "%d",
 803                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 804       }
 805
 806   fprintf (file, "\n");
 807 }
 808
 809 void
 810 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
 811 {
 812   unsigned int i, pos;
 813
 814   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 815
 816   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 817     if (TEST_BIT (bmap, i))
 818       {
 819         if (pos > 70)
 820           {
 821             fprintf (file, "\n  ");
 822             pos = 0;
 823           }
 824
 825         fprintf (file, "%d ", i);
 826         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 827       }
 828
 829   fprintf (file, "}\n");
 830 }
 831
 832 DEBUG_FUNCTION void
 833 debug_sbitmap (const_sbitmap bmap)
 834 {
 835   dump_sbitmap_file (stderr, bmap);
 836 }
 837
 838 void
 839 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
 840                      sbitmap *bmaps, int n_maps)
 841 {
 842   int i;
 843
 844   fprintf (file, "%s\n", title);
 845   for (i = 0; i < n_maps; i++)
 846     {
 847       fprintf (file, "%s %d\n", subtitle, i);
 848       dump_sbitmap (file, bmaps[i]);
 849     }
 850
 851   fprintf (file, "\n");
 852 }
 853
 854 #if GCC_VERSION < 3400
 855 /* Table of number of set bits in a character, indexed by value of char.  */
 856 static const unsigned char popcount_table[] =
 857 {
 858     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,
 859     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,
 860     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,
 861     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,
 862     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,
 863     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,
 864     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,
 865     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,
 866 };
 867
 868 /* Count the bits in an SBITMAP element A.  */
 869
 870 static unsigned long
 871 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
 872 {
 873   unsigned long ret = 0;
 874   unsigned i;
 875
 876   if (a == 0)
 877     return 0;
 878
 879   /* Just do this the table way for now  */
 880   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
 881     ret += popcount_table[(a >> i) & 0xff];
 882   return ret;
 883 }
 884 #endif
 885
 886 /* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
 887
 888 unsigned long
 889 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
 890 {
 891   unsigned long count = 0;
 892   unsigned ix;
 893   unsigned int lastword;
 894
 895   if (maxbit == 0)
 896     return 0;
 897
 898   if (maxbit >= a->n_bits)
 899     maxbit = a->n_bits;
 900
 901   /* Count the bits in the full word.  */
 902   lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
 903   for (ix = 0; ix < lastword; ix++)
 904     {
 905       if (a->popcount)
 906         {
 907           count += a->popcount[ix];
 908 #ifdef BITMAP_DEBUGGING
 909           gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
 910 #endif
 911         }
 912       else
 913         count += do_popcount (a->elms[ix]);
 914     }
 915
 916   /* Count the remaining bits.  */
 917   if (lastword < a->size)
 918     {
 919       unsigned int bitindex;
 920       SBITMAP_ELT_TYPE theword = a->elms[lastword];
 921
 922       bitindex = maxbit % SBITMAP_ELT_BITS;
 923       if (bitindex != 0)
 924         {
 925           theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
 926           count += do_popcount (theword);
 927         }
 928     }
 929   return count;
 930 }
 931