gcc/sbitmap.c

   1 /* Simple bitmaps.
   2    Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008
   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 "tm.h"
  25 #include "rtl.h"
  26 #include "flags.h"
  27 #include "hard-reg-set.h"
  28 #include "obstack.h"
  29 #include "basic-block.h"
  30
  31 #if GCC_VERSION >= 3400
  32 #if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
  33 #define do_popcount(x) __builtin_popcountl(x)
  34 #elif HOST_BITS_PER_WIDEST_FAST_INT == 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 /* This macro controls debugging that is as expensive as the
  45    operations it verifies.  */
  46
  47 /* #define BITMAP_DEBUGGING  */
  48 #ifdef BITMAP_DEBUGGING
  49
  50 /* Verify the population count of sbitmap A matches the cached value,
  51    if there is a cached value. */
  52
  53 void
  54 sbitmap_verify_popcount (const_sbitmap a)
  55 {
  56   unsigned ix;
  57   unsigned int lastword;
  58
  59   if (!a->popcount)
  60     return;
  61
  62   lastword = a->size;
  63   for (ix = 0; ix < lastword; ix++)
  64     gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
  65 }
  66 #endif
  67
  68 /* Bitmap manipulation routines.  */
  69
  70 /* Allocate a simple bitmap of N_ELMS bits.  */
  71
  72 sbitmap
  73 sbitmap_alloc (unsigned int n_elms)
  74 {
  75   unsigned int bytes, size, amt;
  76   sbitmap bmap;
  77
  78   size = SBITMAP_SET_SIZE (n_elms);
  79   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  80   amt = (sizeof (struct simple_bitmap_def)
  81          + bytes - sizeof (SBITMAP_ELT_TYPE));
  82   bmap = xmalloc (amt);
  83   bmap->n_bits = n_elms;
  84   bmap->size = size;
  85   bmap->popcount = NULL;
  86   return bmap;
  87 }
  88
  89 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array.  */
  90
  91 sbitmap
  92 sbitmap_alloc_with_popcount (unsigned int n_elms)
  93 {
  94   sbitmap const bmap = sbitmap_alloc (n_elms);
  95   bmap->popcount = xmalloc (bmap->size * sizeof (unsigned char));
  96   return bmap;
  97 }
  98
  99 /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
 100    size of BMAP, clear the new bits to zero if the DEF argument
 101    is zero, and set them to one otherwise.  */
 102
 103 sbitmap
 104 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
 105 {
 106   unsigned int bytes, size, amt;
 107   unsigned int last_bit;
 108
 109   size = SBITMAP_SET_SIZE (n_elms);
 110   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 111   if (bytes > SBITMAP_SIZE_BYTES (bmap))
 112     {
 113       amt = (sizeof (struct simple_bitmap_def)
 114             + bytes - sizeof (SBITMAP_ELT_TYPE));
 115       bmap = xrealloc (bmap, amt);
 116       if (bmap->popcount)
 117         bmap->popcount = xrealloc (bmap->popcount,
 118                                    size * sizeof (unsigned char));
 119     }
 120
 121   if (n_elms > bmap->n_bits)
 122     {
 123       if (def)
 124         {
 125           memset (bmap->elms + bmap->size, -1,
 126                   bytes - SBITMAP_SIZE_BYTES (bmap));
 127
 128           /* Set the new bits if the original last element.  */
 129           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 130           if (last_bit)
 131             bmap->elms[bmap->size - 1]
 132               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 133
 134           /* Clear the unused bit in the new last element.  */
 135           last_bit = n_elms % SBITMAP_ELT_BITS;
 136           if (last_bit)
 137             bmap->elms[size - 1]
 138               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 139         }
 140       else
 141         {
 142           memset (bmap->elms + bmap->size, 0,
 143                   bytes - SBITMAP_SIZE_BYTES (bmap));
 144           if (bmap->popcount)
 145             memset (bmap->popcount + bmap->size, 0,
 146                     (size * sizeof (unsigned char))
 147                     - (bmap->size * sizeof (unsigned char)));
 148
 149         }
 150     }
 151   else if (n_elms < bmap->n_bits)
 152     {
 153       /* Clear the surplus bits in the last word.  */
 154       last_bit = n_elms % SBITMAP_ELT_BITS;
 155       if (last_bit)
 156         {
 157           bmap->elms[size - 1]
 158             &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 159           if (bmap->popcount)
 160             bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
 161         }
 162     }
 163
 164   bmap->n_bits = n_elms;
 165   bmap->size = size;
 166   return bmap;
 167 }
 168
 169 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 170
 171 sbitmap
 172 sbitmap_realloc (sbitmap src, unsigned int n_elms)
 173 {
 174   unsigned int bytes, size, amt;
 175   sbitmap bmap;
 176
 177   size = SBITMAP_SET_SIZE (n_elms);
 178   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 179   amt = (sizeof (struct simple_bitmap_def)
 180          + bytes - sizeof (SBITMAP_ELT_TYPE));
 181
 182   if (SBITMAP_SIZE_BYTES (src)  >= bytes)
 183     {
 184       src->n_bits = n_elms;
 185       return src;
 186     }
 187
 188   bmap = (sbitmap) xrealloc (src, amt);
 189   bmap->n_bits = n_elms;
 190   bmap->size = size;
 191   return bmap;
 192 }
 193
 194 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 195
 196 sbitmap *
 197 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
 198 {
 199   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
 200   sbitmap *bitmap_vector;
 201
 202   size = SBITMAP_SET_SIZE (n_elms);
 203   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 204   elm_bytes = (sizeof (struct simple_bitmap_def)
 205                + bytes - sizeof (SBITMAP_ELT_TYPE));
 206   vector_bytes = n_vecs * sizeof (sbitmap *);
 207
 208   /* Round up `vector_bytes' to account for the alignment requirements
 209      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
 210      separately, but that requires maintaining two pointers or creating
 211      a cover struct to hold both pointers (so our result is still just
 212      one pointer).  Neither is a bad idea, but this is simpler for now.  */
 213   {
 214     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
 215     struct { char x; SBITMAP_ELT_TYPE y; } align;
 216     int alignment = (char *) & align.y - & align.x;
 217     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
 218   }
 219
 220   amt = vector_bytes + (n_vecs * elm_bytes);
 221   bitmap_vector = xmalloc (amt);
 222
 223   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
 224     {
 225       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 226
 227       bitmap_vector[i] = b;
 228       b->n_bits = n_elms;
 229       b->size = size;
 230       b->popcount = NULL;
 231     }
 232
 233   return bitmap_vector;
 234 }
 235
 236 /* Copy sbitmap SRC to DST.  */
 237
 238 void
 239 sbitmap_copy (sbitmap dst, const_sbitmap src)
 240 {
 241   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
 242   if (dst->popcount)
 243     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
 244 }
 245
 246 /* Copy the first N elements of sbitmap SRC to DST.  */
 247
 248 void
 249 sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
 250 {
 251   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
 252   if (dst->popcount)
 253     memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
 254 }
 255
 256 /* Determine if a == b.  */
 257 int
 258 sbitmap_equal (const_sbitmap a, const_sbitmap b)
 259 {
 260   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
 261 }
 262
 263 /* Return true if the bitmap is empty.  */
 264
 265 bool
 266 sbitmap_empty_p (const_sbitmap bmap)
 267 {
 268   unsigned int i;
 269   for (i=0; i<bmap->size; i++)
 270     if (bmap->elms[i])
 271       return false;
 272
 273   return true;
 274 }
 275
 276 /* Return false if any of the N bits are set in MAP starting at
 277    START.  */
 278
 279 bool
 280 sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n)
 281 {
 282   unsigned int i = start / SBITMAP_ELT_BITS;
 283   SBITMAP_ELT_TYPE elm;
 284   unsigned int shift = start % SBITMAP_ELT_BITS;
 285
 286   gcc_assert (bmap->n_bits >= start + n);
 287
 288   elm = bmap->elms[i];
 289   elm = elm >> shift;
 290
 291   if (shift + n <= SBITMAP_ELT_BITS)
 292     {
 293       /* The bits are totally contained in a single element.  */
 294       if (shift + n < SBITMAP_ELT_BITS)
 295         elm &= ((1 << n) - 1);
 296       return (elm == 0);
 297     }
 298
 299   if (elm)
 300     return false;
 301
 302   n -= SBITMAP_ELT_BITS - shift;
 303   i++;
 304
 305   /* Deal with full elts.  */
 306   while (n >= SBITMAP_ELT_BITS)
 307     {
 308       if (bmap->elms[i])
 309         return false;
 310       i++;
 311       n -= SBITMAP_ELT_BITS;
 312     }
 313
 314   /* The leftover bits.  */
 315   if (n)
 316     {
 317       elm = bmap->elms[i];
 318       elm &= ((1 << n) - 1);
 319       return (elm == 0);
 320     }
 321
 322   return true;
 323 }
 324
 325
 326
 327 /* Zero all elements in a bitmap.  */
 328
 329 void
 330 sbitmap_zero (sbitmap bmap)
 331 {
 332   memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
 333   if (bmap->popcount)
 334     memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
 335 }
 336
 337 /* Set all elements in a bitmap to ones.  */
 338
 339 void
 340 sbitmap_ones (sbitmap bmap)
 341 {
 342   unsigned int last_bit;
 343
 344   memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
 345   if (bmap->popcount)
 346     memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
 347
 348   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 349   if (last_bit)
 350     {
 351       bmap->elms[bmap->size - 1]
 352         = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 353       if (bmap->popcount)
 354         bmap->popcount[bmap->size - 1]
 355           = do_popcount (bmap->elms[bmap->size - 1]);
 356     }
 357 }
 358
 359 /* Zero a vector of N_VECS bitmaps.  */
 360
 361 void
 362 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
 363 {
 364   unsigned int i;
 365
 366   for (i = 0; i < n_vecs; i++)
 367     sbitmap_zero (bmap[i]);
 368 }
 369
 370 /* Set a vector of N_VECS bitmaps to ones.  */
 371
 372 void
 373 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 374 {
 375   unsigned int i;
 376
 377   for (i = 0; i < n_vecs; i++)
 378     sbitmap_ones (bmap[i]);
 379 }
 380
 381 /* Set DST to be A union (B - C).
 382    DST = A | (B & ~C).
 383    Returns true if any change is made.  */
 384
 385 bool
 386 sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 387 {
 388   unsigned int i, n = dst->size;
 389   sbitmap_ptr dstp = dst->elms;
 390   const_sbitmap_ptr ap = a->elms;
 391   const_sbitmap_ptr bp = b->elms;
 392   const_sbitmap_ptr cp = c->elms;
 393   SBITMAP_ELT_TYPE changed = 0;
 394
 395   gcc_assert (!dst->popcount);
 396
 397   for (i = 0; i < n; i++)
 398     {
 399       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 400       changed |= *dstp ^ tmp;
 401       *dstp++ = tmp;
 402     }
 403
 404   return changed != 0;
 405 }
 406
 407 void
 408 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 409 {
 410   unsigned int i, n = dst->size;
 411   sbitmap_ptr dstp = dst->elms;
 412   const_sbitmap_ptr ap = a->elms;
 413   const_sbitmap_ptr bp = b->elms;
 414   const_sbitmap_ptr cp = c->elms;
 415
 416   gcc_assert (!dst->popcount && !a->popcount
 417               && !b->popcount && !c->popcount);
 418
 419   for (i = 0; i < n; i++)
 420     *dstp++ = *ap++ | (*bp++ & ~*cp++);
 421 }
 422
 423 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 424
 425 void
 426 sbitmap_not (sbitmap dst, const_sbitmap src)
 427 {
 428   unsigned int i, n = dst->size;
 429   sbitmap_ptr dstp = dst->elms;
 430   const_sbitmap_ptr srcp = src->elms;
 431   unsigned int last_bit;
 432
 433   gcc_assert (!dst->popcount);
 434
 435   for (i = 0; i < n; i++)
 436     *dstp++ = ~*srcp++;
 437
 438   /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
 439   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 440   if (last_bit)
 441     dst->elms[n-1] = dst->elms[n-1]
 442       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 443 }
 444
 445 /* Set the bits in DST to be the difference between the bits
 446    in A and the bits in B. i.e. dst = a & (~b).  */
 447
 448 void
 449 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
 450 {
 451   unsigned int i, dst_size = dst->size;
 452   unsigned int min_size = dst->size;
 453   sbitmap_ptr dstp = dst->elms;
 454   const_sbitmap_ptr ap = a->elms;
 455   const_sbitmap_ptr bp = b->elms;
 456
 457   gcc_assert (!dst->popcount);
 458
 459   /* A should be at least as large as DEST, to have a defined source.  */
 460   gcc_assert (a->size >= dst_size);
 461   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 462      only copy the subtrahend into dest.  */
 463   if (b->size < min_size)
 464     min_size = b->size;
 465   for (i = 0; i < min_size; i++)
 466     *dstp++ = *ap++ & (~*bp++);
 467   /* Now fill the rest of dest from A, if B was too short.
 468      This makes sense only when destination and A differ.  */
 469   if (dst != a && i != dst_size)
 470     for (; i < dst_size; i++)
 471       *dstp++ = *ap++;
 472 }
 473
 474 /* Return true if there are any bits set in A are also set in B.
 475    Return false otherwise.  */
 476
 477 bool
 478 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
 479 {
 480   const_sbitmap_ptr ap = a->elms;
 481   const_sbitmap_ptr bp = b->elms;
 482   unsigned int i, n;
 483
 484   n = MIN (a->size, b->size);
 485   for (i = 0; i < n; i++)
 486     if ((*ap++ & *bp++) != 0)
 487       return true;
 488
 489   return false;
 490 }
 491
 492 /* Set DST to be (A and B).
 493    Return nonzero if any change is made.  */
 494
 495 bool
 496 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 497 {
 498   unsigned int i, n = dst->size;
 499   sbitmap_ptr dstp = dst->elms;
 500   const_sbitmap_ptr ap = a->elms;
 501   const_sbitmap_ptr bp = b->elms;
 502   SBITMAP_ELT_TYPE changed = 0;
 503
 504   gcc_assert (!dst->popcount);
 505
 506   for (i = 0; i < n; i++)
 507     {
 508       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 509       changed |= *dstp ^ tmp;
 510       *dstp++ = tmp;
 511     }
 512
 513   return changed != 0;
 514 }
 515
 516 void
 517 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 518 {
 519   unsigned int i, n = dst->size;
 520   sbitmap_ptr dstp = dst->elms;
 521   const_sbitmap_ptr ap = a->elms;
 522   const_sbitmap_ptr bp = b->elms;
 523   bool has_popcount = dst->popcount != NULL;
 524   unsigned char *popcountp = dst->popcount;
 525
 526   for (i = 0; i < n; i++)
 527     {
 528       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 529       if (has_popcount)
 530         {
 531           bool wordchanged = (*dstp ^ tmp) != 0;
 532           if (wordchanged)
 533             *popcountp = do_popcount (tmp);
 534           popcountp++;
 535         }
 536       *dstp++ = tmp;
 537     }
 538 #ifdef BITMAP_DEBUGGING
 539   if (has_popcount)
 540     sbitmap_verify_popcount (dst);
 541 #endif
 542 }
 543
 544 /* Set DST to be (A xor B)).
 545    Return nonzero if any change is made.  */
 546
 547 bool
 548 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 549 {
 550   unsigned int i, n = dst->size;
 551   sbitmap_ptr dstp = dst->elms;
 552   const_sbitmap_ptr ap = a->elms;
 553   const_sbitmap_ptr bp = b->elms;
 554   SBITMAP_ELT_TYPE changed = 0;
 555
 556   gcc_assert (!dst->popcount);
 557
 558   for (i = 0; i < n; i++)
 559     {
 560       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 561       changed |= *dstp ^ tmp;
 562       *dstp++ = tmp;
 563     }
 564
 565   return changed != 0;
 566 }
 567
 568 void
 569 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 570 {
 571   unsigned int i, n = dst->size;
 572   sbitmap_ptr dstp = dst->elms;
 573   const_sbitmap_ptr ap = a->elms;
 574   const_sbitmap_ptr bp = b->elms;
 575   bool has_popcount = dst->popcount != NULL;
 576   unsigned char *popcountp = dst->popcount;
 577
 578   for (i = 0; i < n; i++)
 579     {
 580       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 581       if (has_popcount)
 582         {
 583           bool wordchanged = (*dstp ^ tmp) != 0;
 584           if (wordchanged)
 585             *popcountp = do_popcount (tmp);
 586           popcountp++;
 587         }
 588       *dstp++ = tmp;
 589     }
 590 #ifdef BITMAP_DEBUGGING
 591   if (has_popcount)
 592     sbitmap_verify_popcount (dst);
 593 #endif
 594 }
 595
 596 /* Set DST to be (A or B)).
 597    Return nonzero if any change is made.  */
 598
 599 bool
 600 sbitmap_a_or_b_cg (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   gcc_assert (!dst->popcount);
 609
 610   for (i = 0; i < n; i++)
 611     {
 612       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 613       changed |= *dstp ^ tmp;
 614       *dstp++ = tmp;
 615     }
 616
 617   return changed != 0;
 618 }
 619
 620 void
 621 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 622 {
 623   unsigned int i, n = dst->size;
 624   sbitmap_ptr dstp = dst->elms;
 625   const_sbitmap_ptr ap = a->elms;
 626   const_sbitmap_ptr bp = b->elms;
 627   bool has_popcount = dst->popcount != NULL;
 628   unsigned char *popcountp = dst->popcount;
 629
 630   for (i = 0; i < n; i++)
 631     {
 632       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 633       if (has_popcount)
 634         {
 635           bool wordchanged = (*dstp ^ tmp) != 0;
 636           if (wordchanged)
 637             *popcountp = do_popcount (tmp);
 638           popcountp++;
 639         }
 640       *dstp++ = tmp;
 641     }
 642 #ifdef BITMAP_DEBUGGING
 643   if (has_popcount)
 644     sbitmap_verify_popcount (dst);
 645 #endif
 646 }
 647
 648 /* Return nonzero if A is a subset of B.  */
 649
 650 bool
 651 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
 652 {
 653   unsigned int i, n = a->size;
 654   const_sbitmap_ptr ap, bp;
 655
 656   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 657     if ((*ap | *bp) != *bp)
 658       return false;
 659
 660   return true;
 661 }
 662
 663 /* Set DST to be (A or (B and C)).
 664    Return nonzero if any change is made.  */
 665
 666 bool
 667 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 668 {
 669   unsigned int i, n = dst->size;
 670   sbitmap_ptr dstp = dst->elms;
 671   const_sbitmap_ptr ap = a->elms;
 672   const_sbitmap_ptr bp = b->elms;
 673   const_sbitmap_ptr cp = c->elms;
 674   SBITMAP_ELT_TYPE changed = 0;
 675
 676   gcc_assert (!dst->popcount);
 677
 678   for (i = 0; i < n; i++)
 679     {
 680       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 681       changed |= *dstp ^ tmp;
 682       *dstp++ = tmp;
 683     }
 684
 685   return changed != 0;
 686 }
 687
 688 void
 689 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 690 {
 691   unsigned int i, n = dst->size;
 692   sbitmap_ptr dstp = dst->elms;
 693   const_sbitmap_ptr ap = a->elms;
 694   const_sbitmap_ptr bp = b->elms;
 695   const_sbitmap_ptr cp = c->elms;
 696
 697   gcc_assert (!dst->popcount);
 698
 699   for (i = 0; i < n; i++)
 700     *dstp++ = *ap++ | (*bp++ & *cp++);
 701 }
 702
 703 /* Set DST to be (A and (B or C)).
 704    Return nonzero if any change is made.  */
 705
 706 bool
 707 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 708 {
 709   unsigned int i, n = dst->size;
 710   sbitmap_ptr dstp = dst->elms;
 711   const_sbitmap_ptr ap = a->elms;
 712   const_sbitmap_ptr bp = b->elms;
 713   const_sbitmap_ptr cp = c->elms;
 714   SBITMAP_ELT_TYPE changed = 0;
 715
 716   gcc_assert (!dst->popcount);
 717
 718   for (i = 0; i < n; i++)
 719     {
 720       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 721       changed |= *dstp ^ tmp;
 722       *dstp++ = tmp;
 723     }
 724
 725   return changed != 0;
 726 }
 727
 728 void
 729 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 730 {
 731   unsigned int i, n = dst->size;
 732   sbitmap_ptr dstp = dst->elms;
 733   const_sbitmap_ptr ap = a->elms;
 734   const_sbitmap_ptr bp = b->elms;
 735   const_sbitmap_ptr cp = c->elms;
 736
 737   for (i = 0; i < n; i++)
 738     *dstp++ = *ap++ & (*bp++ | *cp++);
 739 }
 740
 741 #ifdef IN_GCC
 742 /* Set the bitmap DST to the intersection of SRC of successors of
 743    block number BB, using the new flow graph structures.  */
 744
 745 void
 746 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
 747 {
 748   basic_block b = BASIC_BLOCK (bb);
 749   unsigned int set_size = dst->size;
 750   edge e;
 751   unsigned ix;
 752
 753   gcc_assert (!dst->popcount);
 754
 755   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 756     {
 757       e = EDGE_SUCC (b, ix);
 758       if (e->dest == EXIT_BLOCK_PTR)
 759         continue;
 760
 761       sbitmap_copy (dst, src[e->dest->index]);
 762       break;
 763     }
 764
 765   if (e == 0)
 766     sbitmap_ones (dst);
 767   else
 768     for (++ix; ix < EDGE_COUNT (b->succs); ix++)
 769       {
 770         unsigned int i;
 771         sbitmap_ptr p, r;
 772
 773         e = EDGE_SUCC (b, ix);
 774         if (e->dest == EXIT_BLOCK_PTR)
 775           continue;
 776
 777         p = src[e->dest->index]->elms;
 778         r = dst->elms;
 779         for (i = 0; i < set_size; i++)
 780           *r++ &= *p++;
 781       }
 782 }
 783
 784 /* Set the bitmap DST to the intersection of SRC of predecessors of
 785    block number BB, using the new flow graph structures.  */
 786
 787 void
 788 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
 789 {
 790   basic_block b = BASIC_BLOCK (bb);
 791   unsigned int set_size = dst->size;
 792   edge e;
 793   unsigned ix;
 794
 795   gcc_assert (!dst->popcount);
 796
 797   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 798     {
 799       e = EDGE_PRED (b, ix);
 800       if (e->src == ENTRY_BLOCK_PTR)
 801         continue;
 802
 803       sbitmap_copy (dst, src[e->src->index]);
 804       break;
 805     }
 806
 807   if (e == 0)
 808     sbitmap_ones (dst);
 809   else
 810     for (++ix; ix < EDGE_COUNT (b->preds); ix++)
 811       {
 812         unsigned int i;
 813         sbitmap_ptr p, r;
 814
 815         e = EDGE_PRED (b, ix);
 816         if (e->src == ENTRY_BLOCK_PTR)
 817           continue;
 818
 819         p = src[e->src->index]->elms;
 820         r = dst->elms;
 821         for (i = 0; i < set_size; i++)
 822           *r++ &= *p++;
 823       }
 824 }
 825
 826 /* Set the bitmap DST to the union of SRC of successors of
 827    block number BB, using the new flow graph structures.  */
 828
 829 void
 830 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
 831 {
 832   basic_block b = BASIC_BLOCK (bb);
 833   unsigned int set_size = dst->size;
 834   edge e;
 835   unsigned ix;
 836
 837   gcc_assert (!dst->popcount);
 838
 839   for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 840     {
 841       e = EDGE_SUCC (b, ix);
 842       if (e->dest == EXIT_BLOCK_PTR)
 843         continue;
 844
 845       sbitmap_copy (dst, src[e->dest->index]);
 846       break;
 847     }
 848
 849   if (ix == EDGE_COUNT (b->succs))
 850     sbitmap_zero (dst);
 851   else
 852     for (ix++; ix < EDGE_COUNT (b->succs); ix++)
 853       {
 854         unsigned int i;
 855         sbitmap_ptr p, r;
 856
 857         e = EDGE_SUCC (b, ix);
 858         if (e->dest == EXIT_BLOCK_PTR)
 859           continue;
 860
 861         p = src[e->dest->index]->elms;
 862         r = dst->elms;
 863         for (i = 0; i < set_size; i++)
 864           *r++ |= *p++;
 865       }
 866 }
 867
 868 /* Set the bitmap DST to the union of SRC of predecessors of
 869    block number BB, using the new flow graph structures.  */
 870
 871 void
 872 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
 873 {
 874   basic_block b = BASIC_BLOCK (bb);
 875   unsigned int set_size = dst->size;
 876   edge e;
 877   unsigned ix;
 878
 879   gcc_assert (!dst->popcount);
 880
 881   for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 882     {
 883       e = EDGE_PRED (b, ix);
 884       if (e->src== ENTRY_BLOCK_PTR)
 885         continue;
 886
 887       sbitmap_copy (dst, src[e->src->index]);
 888       break;
 889     }
 890
 891   if (ix == EDGE_COUNT (b->preds))
 892     sbitmap_zero (dst);
 893   else
 894     for (ix++; ix < EDGE_COUNT (b->preds); ix++)
 895       {
 896         unsigned int i;
 897         sbitmap_ptr p, r;
 898
 899         e = EDGE_PRED (b, ix);
 900         if (e->src == ENTRY_BLOCK_PTR)
 901           continue;
 902
 903         p = src[e->src->index]->elms;
 904         r = dst->elms;
 905         for (i = 0; i < set_size; i++)
 906           *r++ |= *p++;
 907       }
 908 }
 909 #endif
 910
 911 /* Return number of first bit set in the bitmap, -1 if none.  */
 912
 913 int
 914 sbitmap_first_set_bit (const_sbitmap bmap)
 915 {
 916   unsigned int n = 0;
 917   sbitmap_iterator sbi;
 918
 919   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
 920     return n;
 921   return -1;
 922 }
 923
 924 /* Return number of last bit set in the bitmap, -1 if none.  */
 925
 926 int
 927 sbitmap_last_set_bit (const_sbitmap bmap)
 928 {
 929   int i;
 930   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 931
 932   for (i = bmap->size - 1; i >= 0; i--)
 933     {
 934       const SBITMAP_ELT_TYPE word = ptr[i];
 935
 936       if (word != 0)
 937         {
 938           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 939           SBITMAP_ELT_TYPE mask
 940             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 941
 942           while (1)
 943             {
 944               if ((word & mask) != 0)
 945                 return index;
 946
 947               mask >>= 1;
 948               index--;
 949             }
 950         }
 951     }
 952
 953   return -1;
 954 }
 955
 956 void
 957 dump_sbitmap (FILE *file, const_sbitmap bmap)
 958 {
 959   unsigned int i, n, j;
 960   unsigned int set_size = bmap->size;
 961   unsigned int total_bits = bmap->n_bits;
 962
 963   fprintf (file, "  ");
 964   for (i = n = 0; i < set_size && n < total_bits; i++)
 965     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 966       {
 967         if (n != 0 && n % 10 == 0)
 968           fprintf (file, " ");
 969
 970         fprintf (file, "%d",
 971                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 972       }
 973
 974   fprintf (file, "\n");
 975 }
 976
 977 void
 978 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
 979 {
 980   unsigned int i, pos;
 981
 982   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 983
 984   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 985     if (TEST_BIT (bmap, i))
 986       {
 987         if (pos > 70)
 988           {
 989             fprintf (file, "\n  ");
 990             pos = 0;
 991           }
 992
 993         fprintf (file, "%d ", i);
 994         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 995       }
 996
 997   fprintf (file, "}\n");
 998 }
 999
1000 void
1001 debug_sbitmap (const_sbitmap bmap)
1002 {
1003   dump_sbitmap_file (stderr, bmap);
1004 }
1005
1006 void
1007 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
1008                      sbitmap *bmaps, int n_maps)
1009 {
1010   int bb;
1011
1012   fprintf (file, "%s\n", title);
1013   for (bb = 0; bb < n_maps; bb++)
1014     {
1015       fprintf (file, "%s %d\n", subtitle, bb);
1016       dump_sbitmap (file, bmaps[bb]);
1017     }
1018
1019   fprintf (file, "\n");
1020 }
1021
1022 #if GCC_VERSION < 3400
1023 /* Table of number of set bits in a character, indexed by value of char.  */
1024 static const unsigned char popcount_table[] =
1025 {
1026     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,
1027     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,
1028     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,
1029     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,
1030     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,
1031     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,
1032     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,
1033     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,
1034 };
1035
1036 /* Count the bits in an SBITMAP element A.  */
1037
1038 static unsigned long
1039 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
1040 {
1041   unsigned long ret = 0;
1042   unsigned i;
1043
1044   if (a == 0)
1045     return 0;
1046
1047   /* Just do this the table way for now  */
1048   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
1049     ret += popcount_table[(a >> i) & 0xff];
1050   return ret;
1051 }
1052 #endif
1053
1054 /* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
1055
1056 unsigned long
1057 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
1058 {
1059   unsigned long count = 0;
1060   unsigned ix;
1061   unsigned int lastword;
1062
1063   if (maxbit == 0)
1064     return 0;
1065
1066   if (maxbit >= a->n_bits)
1067     maxbit = a->n_bits;
1068
1069   /* Count the bits in the full word.  */
1070   lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1071   for (ix = 0; ix < lastword; ix++)
1072     {
1073       if (a->popcount)
1074         {
1075           count += a->popcount[ix];
1076 #ifdef BITMAP_DEBUGGING
1077           gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1078 #endif
1079         }
1080       else
1081         count += do_popcount (a->elms[ix]);
1082     }
1083
1084   /* Count the remaining bits.  */
1085   if (lastword < a->size)
1086     {
1087       unsigned int bitindex;
1088       SBITMAP_ELT_TYPE theword = a->elms[lastword];
1089
1090       bitindex = maxbit % SBITMAP_ELT_BITS;
1091       if (bitindex != 0)
1092         {
1093           theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1094           count += do_popcount (theword);
1095         }
1096     }
1097   return count;
1098 }
1099