gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "sbitmap.h"
  25
  26 /* This suffices for roughly 99% of the hosts we run on, and the rest
  27    don't have 256 bit integers.  */
  28 #if SBITMAP_ELT_BITS > 255
  29 #error Need to increase size of datatype used for popcount
  30 #endif
  31
  32 #if GCC_VERSION >= 3400
  33 #  if SBITMAP_ELT_BITS == HOST_BITS_PER_LONG
  34 #    define do_popcount(x) __builtin_popcountl(x)
  35 #  elif SBITMAP_ELT_BITS == HOST_BITS_PER_LONGLONG
  36 #    define do_popcount(x) __builtin_popcountll(x)
  37 #  else
  38 #    error "internal error: sbitmap.h and hwint.h are inconsistent"
  39 #  endif
  40 #else
  41 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
  42 #  define do_popcount(x) sbitmap_elt_popcount((x))
  43 #endif
  44
  45 typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
  46 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr;
  47
  48 /* This macro controls debugging that is as expensive as the
  49    operations it verifies.  */
  50
  51 /* #define BITMAP_DEBUGGING  */
  52 #ifdef BITMAP_DEBUGGING
  53
  54 /* Verify the population count of sbitmap A matches the cached value,
  55    if there is a cached value. */
  56
  57 void
  58 sbitmap_verify_popcount (const_sbitmap a)
  59 {
  60   unsigned ix;
  61   unsigned int lastword;
  62
  63   if (!a->popcount)
  64     return;
  65
  66   lastword = a->size;
  67   for (ix = 0; ix < lastword; ix++)
  68     gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
  69 }
  70 #endif
  71
  72 /* Bitmap manipulation routines.  */
  73
  74 /* Allocate a simple bitmap of N_ELMS bits.  */
  75
  76 sbitmap
  77 sbitmap_alloc (unsigned int n_elms)
  78 {
  79   unsigned int bytes, size, amt;
  80   sbitmap bmap;
  81
  82   size = SBITMAP_SET_SIZE (n_elms);
  83   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  84   amt = (sizeof (struct simple_bitmap_def)
  85          + bytes - sizeof (SBITMAP_ELT_TYPE));
  86   bmap = (sbitmap) xmalloc (amt);
  87   bmap->n_bits = n_elms;
  88   bmap->size = size;
  89   bmap->popcount = NULL;
  90   return bmap;
  91 }
  92
  93 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array.  */
  94
  95 sbitmap
  96 sbitmap_alloc_with_popcount (unsigned int n_elms)
  97 {
  98   sbitmap const bmap = sbitmap_alloc (n_elms);
  99   bmap->popcount = XNEWVEC (unsigned char, bmap->size);
 100   return bmap;
 101 }
 102
 103 /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
 104    size of BMAP, clear the new bits to zero if the DEF argument
 105    is zero, and set them to one otherwise.  */
 106
 107 sbitmap
 108 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
 109 {
 110   unsigned int bytes, size, amt;
 111   unsigned int last_bit;
 112
 113   size = SBITMAP_SET_SIZE (n_elms);
 114   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 115   if (bytes > SBITMAP_SIZE_BYTES (bmap))
 116     {
 117       amt = (sizeof (struct simple_bitmap_def)
 118             + bytes - sizeof (SBITMAP_ELT_TYPE));
 119       bmap = (sbitmap) xrealloc (bmap, amt);
 120       if (bmap->popcount)
 121         bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size);
 122     }
 123
 124   if (n_elms > bmap->n_bits)
 125     {
 126       if (def)
 127         {
 128           memset (bmap->elms + bmap->size, -1,
 129                   bytes - SBITMAP_SIZE_BYTES (bmap));
 130
 131           /* Set the new bits if the original last element.  */
 132           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 133           if (last_bit)
 134             bmap->elms[bmap->size - 1]
 135               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 136
 137           /* Clear the unused bit in the new last element.  */
 138           last_bit = n_elms % SBITMAP_ELT_BITS;
 139           if (last_bit)
 140             bmap->elms[size - 1]
 141               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 142         }
 143       else
 144         {
 145           memset (bmap->elms + bmap->size, 0,
 146                   bytes - SBITMAP_SIZE_BYTES (bmap));
 147           if (bmap->popcount)
 148             memset (bmap->popcount + bmap->size, 0,
 149                     (size * sizeof (unsigned char))
 150                     - (bmap->size * sizeof (unsigned char)));
 151
 152         }
 153     }
 154   else if (n_elms < bmap->n_bits)
 155     {
 156       /* Clear the surplus bits in the last word.  */
 157       last_bit = n_elms % SBITMAP_ELT_BITS;
 158       if (last_bit)
 159         {
 160           bmap->elms[size - 1]
 161             &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 162           if (bmap->popcount)
 163             bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
 164         }
 165     }
 166
 167   bmap->n_bits = n_elms;
 168   bmap->size = size;
 169   return bmap;
 170 }
 171
 172 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 173
 174 sbitmap
 175 sbitmap_realloc (sbitmap src, unsigned int n_elms)
 176 {
 177   unsigned int bytes, size, amt;
 178   sbitmap bmap;
 179
 180   size = SBITMAP_SET_SIZE (n_elms);
 181   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 182   amt = (sizeof (struct simple_bitmap_def)
 183          + bytes - sizeof (SBITMAP_ELT_TYPE));
 184
 185   if (SBITMAP_SIZE_BYTES (src)  >= bytes)
 186     {
 187       src->n_bits = n_elms;
 188       return src;
 189     }
 190
 191   bmap = (sbitmap) xrealloc (src, amt);
 192   bmap->n_bits = n_elms;
 193   bmap->size = size;
 194   return bmap;
 195 }
 196
 197 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 198
 199 sbitmap *
 200 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
 201 {
 202   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
 203   sbitmap *bitmap_vector;
 204
 205   size = SBITMAP_SET_SIZE (n_elms);
 206   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 207   elm_bytes = (sizeof (struct simple_bitmap_def)
 208                + bytes - sizeof (SBITMAP_ELT_TYPE));
 209   vector_bytes = n_vecs * sizeof (sbitmap *);
 210
 211   /* Round up `vector_bytes' to account for the alignment requirements
 212      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
 213      separately, but that requires maintaining two pointers or creating
 214      a cover struct to hold both pointers (so our result is still just
 215      one pointer).  Neither is a bad idea, but this is simpler for now.  */
 216   {
 217     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
 218     struct { char x; SBITMAP_ELT_TYPE y; } align;
 219     int alignment = (char *) & align.y - & align.x;
 220     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
 221   }
 222
 223   amt = vector_bytes + (n_vecs * elm_bytes);
 224   bitmap_vector = (sbitmap *) xmalloc (amt);
 225
 226   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
 227     {
 228       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 229
 230       bitmap_vector[i] = b;
 231       b->n_bits = n_elms;
 232       b->size = size;
 233       b->popcount = NULL;
 234     }
 235
 236   return bitmap_vector;
 237 }
 238
 239 /* Copy sbitmap SRC to DST.  */
 240
 241 void
 242 sbitmap_copy (sbitmap dst, const_sbitmap src)
 243 {
 244   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
 245   if (dst->popcount)
 246     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
 247 }
 248
 249 /* Copy the first N elements of sbitmap SRC to DST.  */
 250
 251 void
 252 sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
 253 {
 254   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
 255   if (dst->popcount)
 256     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
 257 }
 258
 259 /* Determine if a == b.  */
 260 int
 261 sbitmap_equal (const_sbitmap a, const_sbitmap b)
 262 {
 263   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
 264 }
 265
 266 /* Return true if the bitmap is empty.  */
 267
 268 bool
 269 sbitmap_empty_p (const_sbitmap bmap)
 270 {
 271   unsigned int i;
 272   for (i=0; i<bmap->size; i++)
 273     if (bmap->elms[i])
 274       return false;
 275
 276   return true;
 277 }
 278
 279 /* Return false if any of the N bits are set in MAP starting at
 280    START.  */
 281
 282 bool
 283 sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n)
 284 {
 285   unsigned int i = start / SBITMAP_ELT_BITS;
 286   SBITMAP_ELT_TYPE elm;
 287   unsigned int shift = start % SBITMAP_ELT_BITS;
 288
 289   gcc_assert (bmap->n_bits >= start + n);
 290
 291   elm = bmap->elms[i];
 292   elm = elm >> shift;
 293
 294   if (shift + n <= SBITMAP_ELT_BITS)
 295     {
 296       /* The bits are totally contained in a single element.  */
 297       if (shift + n < SBITMAP_ELT_BITS)
 298         elm &= ((1 << n) - 1);
 299       return (elm == 0);
 300     }
 301
 302   if (elm)
 303     return false;
 304
 305   n -= SBITMAP_ELT_BITS - shift;
 306   i++;
 307
 308   /* Deal with full elts.  */
 309   while (n >= SBITMAP_ELT_BITS)
 310     {
 311       if (bmap->elms[i])
 312         return false;
 313       i++;
 314       n -= SBITMAP_ELT_BITS;
 315     }
 316
 317   /* The leftover bits.  */
 318   if (n)
 319     {
 320       elm = bmap->elms[i];
 321       elm &= ((1 << n) - 1);
 322       return (elm == 0);
 323     }
 324
 325   return true;
 326 }
 327
 328
 329
 330 /* Zero all elements in a bitmap.  */
 331
 332 void
 333 sbitmap_zero (sbitmap bmap)
 334 {
 335   memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
 336   if (bmap->popcount)
 337     memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
 338 }
 339
 340 /* Set all elements in a bitmap to ones.  */
 341
 342 void
 343 sbitmap_ones (sbitmap bmap)
 344 {
 345   unsigned int last_bit;
 346
 347   memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
 348   if (bmap->popcount)
 349     memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
 350
 351   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 352   if (last_bit)
 353     {
 354       bmap->elms[bmap->size - 1]
 355         = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 356       if (bmap->popcount)
 357         bmap->popcount[bmap->size - 1]
 358           = do_popcount (bmap->elms[bmap->size - 1]);
 359     }
 360 }
 361
 362 /* Zero a vector of N_VECS bitmaps.  */
 363
 364 void
 365 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
 366 {
 367   unsigned int i;
 368
 369   for (i = 0; i < n_vecs; i++)
 370     sbitmap_zero (bmap[i]);
 371 }
 372
 373 /* Set a vector of N_VECS bitmaps to ones.  */
 374
 375 void
 376 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 377 {
 378   unsigned int i;
 379
 380   for (i = 0; i < n_vecs; i++)
 381     sbitmap_ones (bmap[i]);
 382 }
 383
 384 /* Set DST to be A union (B - C).
 385    DST = A | (B & ~C).
 386    Returns true if any change is made.  */
 387
 388 bool
 389 sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 390 {
 391   unsigned int i, n = dst->size;
 392   sbitmap_ptr dstp = dst->elms;
 393   const_sbitmap_ptr ap = a->elms;
 394   const_sbitmap_ptr bp = b->elms;
 395   const_sbitmap_ptr cp = c->elms;
 396   SBITMAP_ELT_TYPE changed = 0;
 397
 398   gcc_assert (!dst->popcount);
 399
 400   for (i = 0; i < n; i++)
 401     {
 402       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 403       changed |= *dstp ^ tmp;
 404       *dstp++ = tmp;
 405     }
 406
 407   return changed != 0;
 408 }
 409
 410 void
 411 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 412 {
 413   unsigned int i, n = dst->size;
 414   sbitmap_ptr dstp = dst->elms;
 415   const_sbitmap_ptr ap = a->elms;
 416   const_sbitmap_ptr bp = b->elms;
 417   const_sbitmap_ptr cp = c->elms;
 418
 419   gcc_assert (!dst->popcount && !a->popcount
 420               && !b->popcount && !c->popcount);
 421
 422   for (i = 0; i < n; i++)
 423     *dstp++ = *ap++ | (*bp++ & ~*cp++);
 424 }
 425
 426 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 427
 428 void
 429 sbitmap_not (sbitmap dst, const_sbitmap src)
 430 {
 431   unsigned int i, n = dst->size;
 432   sbitmap_ptr dstp = dst->elms;
 433   const_sbitmap_ptr srcp = src->elms;
 434   unsigned int last_bit;
 435
 436   gcc_assert (!dst->popcount);
 437
 438   for (i = 0; i < n; i++)
 439     *dstp++ = ~*srcp++;
 440
 441   /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
 442   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 443   if (last_bit)
 444     dst->elms[n-1] = dst->elms[n-1]
 445       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 446 }
 447
 448 /* Set the bits in DST to be the difference between the bits
 449    in A and the bits in B. i.e. dst = a & (~b).  */
 450
 451 void
 452 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
 453 {
 454   unsigned int i, dst_size = dst->size;
 455   unsigned int min_size = dst->size;
 456   sbitmap_ptr dstp = dst->elms;
 457   const_sbitmap_ptr ap = a->elms;
 458   const_sbitmap_ptr bp = b->elms;
 459
 460   gcc_assert (!dst->popcount);
 461
 462   /* A should be at least as large as DEST, to have a defined source.  */
 463   gcc_assert (a->size >= dst_size);
 464   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 465      only copy the subtrahend into dest.  */
 466   if (b->size < min_size)
 467     min_size = b->size;
 468   for (i = 0; i < min_size; i++)
 469     *dstp++ = *ap++ & (~*bp++);
 470   /* Now fill the rest of dest from A, if B was too short.
 471      This makes sense only when destination and A differ.  */
 472   if (dst != a && i != dst_size)
 473     for (; i < dst_size; i++)
 474       *dstp++ = *ap++;
 475 }
 476
 477 /* Return true if there are any bits set in A are also set in B.
 478    Return false otherwise.  */
 479
 480 bool
 481 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
 482 {
 483   const_sbitmap_ptr ap = a->elms;
 484   const_sbitmap_ptr bp = b->elms;
 485   unsigned int i, n;
 486
 487   n = MIN (a->size, b->size);
 488   for (i = 0; i < n; i++)
 489     if ((*ap++ & *bp++) != 0)
 490       return true;
 491
 492   return false;
 493 }
 494
 495 /* Set DST to be (A and B).
 496    Return nonzero if any change is made.  */
 497
 498 bool
 499 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 500 {
 501   unsigned int i, n = dst->size;
 502   sbitmap_ptr dstp = dst->elms;
 503   const_sbitmap_ptr ap = a->elms;
 504   const_sbitmap_ptr bp = b->elms;
 505   SBITMAP_ELT_TYPE changed = 0;
 506
 507   gcc_assert (!dst->popcount);
 508
 509   for (i = 0; i < n; i++)
 510     {
 511       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 512       changed |= *dstp ^ tmp;
 513       *dstp++ = tmp;
 514     }
 515
 516   return changed != 0;
 517 }
 518
 519 void
 520 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 521 {
 522   unsigned int i, n = dst->size;
 523   sbitmap_ptr dstp = dst->elms;
 524   const_sbitmap_ptr ap = a->elms;
 525   const_sbitmap_ptr bp = b->elms;
 526   bool has_popcount = dst->popcount != NULL;
 527   unsigned char *popcountp = dst->popcount;
 528
 529   for (i = 0; i < n; i++)
 530     {
 531       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 532       if (has_popcount)
 533         {
 534           bool wordchanged = (*dstp ^ tmp) != 0;
 535           if (wordchanged)
 536             *popcountp = do_popcount (tmp);
 537           popcountp++;
 538         }
 539       *dstp++ = tmp;
 540     }
 541 #ifdef BITMAP_DEBUGGING
 542   if (has_popcount)
 543     sbitmap_verify_popcount (dst);
 544 #endif
 545 }
 546
 547 /* Set DST to be (A xor B)).
 548    Return nonzero if any change is made.  */
 549
 550 bool
 551 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 552 {
 553   unsigned int i, n = dst->size;
 554   sbitmap_ptr dstp = dst->elms;
 555   const_sbitmap_ptr ap = a->elms;
 556   const_sbitmap_ptr bp = b->elms;
 557   SBITMAP_ELT_TYPE changed = 0;
 558
 559   gcc_assert (!dst->popcount);
 560
 561   for (i = 0; i < n; i++)
 562     {
 563       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 564       changed |= *dstp ^ tmp;
 565       *dstp++ = tmp;
 566     }
 567
 568   return changed != 0;
 569 }
 570
 571 void
 572 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 573 {
 574   unsigned int i, n = dst->size;
 575   sbitmap_ptr dstp = dst->elms;
 576   const_sbitmap_ptr ap = a->elms;
 577   const_sbitmap_ptr bp = b->elms;
 578   bool has_popcount = dst->popcount != NULL;
 579   unsigned char *popcountp = dst->popcount;
 580
 581   for (i = 0; i < n; i++)
 582     {
 583       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 584       if (has_popcount)
 585         {
 586           bool wordchanged = (*dstp ^ tmp) != 0;
 587           if (wordchanged)
 588             *popcountp = do_popcount (tmp);
 589           popcountp++;
 590         }
 591       *dstp++ = tmp;
 592     }
 593 #ifdef BITMAP_DEBUGGING
 594   if (has_popcount)
 595     sbitmap_verify_popcount (dst);
 596 #endif
 597 }
 598
 599 /* Set DST to be (A or B)).
 600    Return nonzero if any change is made.  */
 601
 602 bool
 603 sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 604 {
 605   unsigned int i, n = dst->size;
 606   sbitmap_ptr dstp = dst->elms;
 607   const_sbitmap_ptr ap = a->elms;
 608   const_sbitmap_ptr bp = b->elms;
 609   SBITMAP_ELT_TYPE changed = 0;
 610
 611   gcc_assert (!dst->popcount);
 612
 613   for (i = 0; i < n; i++)
 614     {
 615       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 616       changed |= *dstp ^ tmp;
 617       *dstp++ = tmp;
 618     }
 619
 620   return changed != 0;
 621 }
 622
 623 void
 624 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 625 {
 626   unsigned int i, n = dst->size;
 627   sbitmap_ptr dstp = dst->elms;
 628   const_sbitmap_ptr ap = a->elms;
 629   const_sbitmap_ptr bp = b->elms;
 630   bool has_popcount = dst->popcount != NULL;
 631   unsigned char *popcountp = dst->popcount;
 632
 633   for (i = 0; i < n; i++)
 634     {
 635       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 636       if (has_popcount)
 637         {
 638           bool wordchanged = (*dstp ^ tmp) != 0;
 639           if (wordchanged)
 640             *popcountp = do_popcount (tmp);
 641           popcountp++;
 642         }
 643       *dstp++ = tmp;
 644     }
 645 #ifdef BITMAP_DEBUGGING
 646   if (has_popcount)
 647     sbitmap_verify_popcount (dst);
 648 #endif
 649 }
 650
 651 /* Return nonzero if A is a subset of B.  */
 652
 653 bool
 654 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
 655 {
 656   unsigned int i, n = a->size;
 657   const_sbitmap_ptr ap, bp;
 658
 659   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 660     if ((*ap | *bp) != *bp)
 661       return false;
 662
 663   return true;
 664 }
 665
 666 /* Set DST to be (A or (B and C)).
 667    Return nonzero if any change is made.  */
 668
 669 bool
 670 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 671 {
 672   unsigned int i, n = dst->size;
 673   sbitmap_ptr dstp = dst->elms;
 674   const_sbitmap_ptr ap = a->elms;
 675   const_sbitmap_ptr bp = b->elms;
 676   const_sbitmap_ptr cp = c->elms;
 677   SBITMAP_ELT_TYPE changed = 0;
 678
 679   gcc_assert (!dst->popcount);
 680
 681   for (i = 0; i < n; i++)
 682     {
 683       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 684       changed |= *dstp ^ tmp;
 685       *dstp++ = tmp;
 686     }
 687
 688   return changed != 0;
 689 }
 690
 691 void
 692 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 693 {
 694   unsigned int i, n = dst->size;
 695   sbitmap_ptr dstp = dst->elms;
 696   const_sbitmap_ptr ap = a->elms;
 697   const_sbitmap_ptr bp = b->elms;
 698   const_sbitmap_ptr cp = c->elms;
 699
 700   gcc_assert (!dst->popcount);
 701
 702   for (i = 0; i < n; i++)
 703     *dstp++ = *ap++ | (*bp++ & *cp++);
 704 }
 705
 706 /* Set DST to be (A and (B or C)).
 707    Return nonzero if any change is made.  */
 708
 709 bool
 710 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 711 {
 712   unsigned int i, n = dst->size;
 713   sbitmap_ptr dstp = dst->elms;
 714   const_sbitmap_ptr ap = a->elms;
 715   const_sbitmap_ptr bp = b->elms;
 716   const_sbitmap_ptr cp = c->elms;
 717   SBITMAP_ELT_TYPE changed = 0;
 718
 719   gcc_assert (!dst->popcount);
 720
 721   for (i = 0; i < n; i++)
 722     {
 723       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 724       changed |= *dstp ^ tmp;
 725       *dstp++ = tmp;
 726     }
 727
 728   return changed != 0;
 729 }
 730
 731 void
 732 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 733 {
 734   unsigned int i, n = dst->size;
 735   sbitmap_ptr dstp = dst->elms;
 736   const_sbitmap_ptr ap = a->elms;
 737   const_sbitmap_ptr bp = b->elms;
 738   const_sbitmap_ptr cp = c->elms;
 739
 740   for (i = 0; i < n; i++)
 741     *dstp++ = *ap++ & (*bp++ | *cp++);
 742 }
 743
 744 /* Return number of first bit set in the bitmap, -1 if none.  */
 745
 746 int
 747 sbitmap_first_set_bit (const_sbitmap bmap)
 748 {
 749   unsigned int n = 0;
 750   sbitmap_iterator sbi;
 751
 752   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
 753     return n;
 754   return -1;
 755 }
 756
 757 /* Return number of last bit set in the bitmap, -1 if none.  */
 758
 759 int
 760 sbitmap_last_set_bit (const_sbitmap bmap)
 761 {
 762   int i;
 763   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 764
 765   for (i = bmap->size - 1; i >= 0; i--)
 766     {
 767       const SBITMAP_ELT_TYPE word = ptr[i];
 768
 769       if (word != 0)
 770         {
 771           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 772           SBITMAP_ELT_TYPE mask
 773             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 774
 775           while (1)
 776             {
 777               if ((word & mask) != 0)
 778                 return index;
 779
 780               mask >>= 1;
 781               index--;
 782             }
 783         }
 784     }
 785
 786   return -1;
 787 }
 788
 789 void
 790 dump_sbitmap (FILE *file, const_sbitmap bmap)
 791 {
 792   unsigned int i, n, j;
 793   unsigned int set_size = bmap->size;
 794   unsigned int total_bits = bmap->n_bits;
 795
 796   fprintf (file, "  ");
 797   for (i = n = 0; i < set_size && n < total_bits; i++)
 798     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 799       {
 800         if (n != 0 && n % 10 == 0)
 801           fprintf (file, " ");
 802
 803         fprintf (file, "%d",
 804                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 805       }
 806
 807   fprintf (file, "\n");
 808 }
 809
 810 void
 811 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
 812 {
 813   unsigned int i, pos;
 814
 815   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 816
 817   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 818     if (TEST_BIT (bmap, i))
 819       {
 820         if (pos > 70)
 821           {
 822             fprintf (file, "\n  ");
 823             pos = 0;
 824           }
 825
 826         fprintf (file, "%d ", i);
 827         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 828       }
 829
 830   fprintf (file, "}\n");
 831 }
 832
 833 DEBUG_FUNCTION void
 834 debug_sbitmap (const_sbitmap bmap)
 835 {
 836   dump_sbitmap_file (stderr, bmap);
 837 }
 838
 839 void
 840 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
 841                      sbitmap *bmaps, int n_maps)
 842 {
 843   int i;
 844
 845   fprintf (file, "%s\n", title);
 846   for (i = 0; i < n_maps; i++)
 847     {
 848       fprintf (file, "%s %d\n", subtitle, i);
 849       dump_sbitmap (file, bmaps[i]);
 850     }
 851
 852   fprintf (file, "\n");
 853 }
 854
 855 #if GCC_VERSION < 3400
 856 /* Table of number of set bits in a character, indexed by value of char.  */
 857 static const unsigned char popcount_table[] =
 858 {
 859     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,
 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     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,
 862     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,
 863     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,
 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     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,
 866     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,
 867 };
 868
 869 /* Count the bits in an SBITMAP element A.  */
 870
 871 static unsigned long
 872 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
 873 {
 874   unsigned long ret = 0;
 875   unsigned i;
 876
 877   if (a == 0)
 878     return 0;
 879
 880   /* Just do this the table way for now  */
 881   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
 882     ret += popcount_table[(a >> i) & 0xff];
 883   return ret;
 884 }
 885 #endif
 886
 887 /* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
 888
 889 unsigned long
 890 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
 891 {
 892   unsigned long count = 0;
 893   unsigned ix;
 894   unsigned int lastword;
 895
 896   if (maxbit == 0)
 897     return 0;
 898
 899   if (maxbit >= a->n_bits)
 900     maxbit = a->n_bits;
 901
 902   /* Count the bits in the full word.  */
 903   lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
 904   for (ix = 0; ix < lastword; ix++)
 905     {
 906       if (a->popcount)
 907         {
 908           count += a->popcount[ix];
 909 #ifdef BITMAP_DEBUGGING
 910           gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
 911 #endif
 912         }
 913       else
 914         count += do_popcount (a->elms[ix]);
 915     }
 916
 917   /* Count the remaining bits.  */
 918   if (lastword < a->size)
 919     {
 920       unsigned int bitindex;
 921       SBITMAP_ELT_TYPE theword = a->elms[lastword];
 922
 923       bitindex = maxbit % SBITMAP_ELT_BITS;
 924       if (bitindex != 0)
 925         {
 926           theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
 927           count += do_popcount (theword);
 928         }
 929     }
 930   return count;
 931 }
 932