gcc/sbitmap.c

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