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