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