gcc/sbitmap.c

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