gcc/sbitmap.c

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