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 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 /* Zero all elements in a bitmap.  */
 277
 278 void
 279 sbitmap_zero (sbitmap bmap)
 280 {
 281   memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
 282   if (bmap->popcount)
 283     memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
 284 }
 285
 286 /* Set all elements in a bitmap to ones.  */
 287
 288 void
 289 sbitmap_ones (sbitmap bmap)
 290 {
 291   unsigned int last_bit;
 292
 293   memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
 294   if (bmap->popcount)
 295     memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
 296
 297   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 298   if (last_bit)
 299     {
 300       bmap->elms[bmap->size - 1]
 301         = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 302       if (bmap->popcount)
 303         bmap->popcount[bmap->size - 1]
 304           = do_popcount (bmap->elms[bmap->size - 1]);
 305     }
 306 }
 307
 308 /* Zero a vector of N_VECS bitmaps.  */
 309
 310 void
 311 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
 312 {
 313   unsigned int i;
 314
 315   for (i = 0; i < n_vecs; i++)
 316     sbitmap_zero (bmap[i]);
 317 }
 318
 319 /* Set a vector of N_VECS bitmaps to ones.  */
 320
 321 void
 322 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 323 {
 324   unsigned int i;
 325
 326   for (i = 0; i < n_vecs; i++)
 327     sbitmap_ones (bmap[i]);
 328 }
 329
 330 /* Set DST to be A union (B - C).
 331    DST = A | (B & ~C).
 332    Returns true if any change is made.  */
 333
 334 bool
 335 sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 336 {
 337   unsigned int i, n = dst->size;
 338   sbitmap_ptr dstp = dst->elms;
 339   const_sbitmap_ptr ap = a->elms;
 340   const_sbitmap_ptr bp = b->elms;
 341   const_sbitmap_ptr cp = c->elms;
 342   SBITMAP_ELT_TYPE changed = 0;
 343
 344   gcc_assert (!dst->popcount);
 345
 346   for (i = 0; i < n; i++)
 347     {
 348       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 349       changed |= *dstp ^ tmp;
 350       *dstp++ = tmp;
 351     }
 352
 353   return changed != 0;
 354 }
 355
 356 void
 357 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 358 {
 359   unsigned int i, n = dst->size;
 360   sbitmap_ptr dstp = dst->elms;
 361   const_sbitmap_ptr ap = a->elms;
 362   const_sbitmap_ptr bp = b->elms;
 363   const_sbitmap_ptr cp = c->elms;
 364
 365   gcc_assert (!dst->popcount && !a->popcount
 366               && !b->popcount && !c->popcount);
 367
 368   for (i = 0; i < n; i++)
 369     *dstp++ = *ap++ | (*bp++ & ~*cp++);
 370 }
 371
 372 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 373
 374 void
 375 sbitmap_not (sbitmap dst, const_sbitmap src)
 376 {
 377   unsigned int i, n = dst->size;
 378   sbitmap_ptr dstp = dst->elms;
 379   const_sbitmap_ptr srcp = src->elms;
 380   unsigned int last_bit;
 381
 382   gcc_assert (!dst->popcount);
 383
 384   for (i = 0; i < n; i++)
 385     *dstp++ = ~*srcp++;
 386
 387   /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
 388   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 389   if (last_bit)
 390     dst->elms[n-1] = dst->elms[n-1]
 391       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 392 }
 393
 394 /* Set the bits in DST to be the difference between the bits
 395    in A and the bits in B. i.e. dst = a & (~b).  */
 396
 397 void
 398 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
 399 {
 400   unsigned int i, dst_size = dst->size;
 401   unsigned int min_size = dst->size;
 402   sbitmap_ptr dstp = dst->elms;
 403   const_sbitmap_ptr ap = a->elms;
 404   const_sbitmap_ptr bp = b->elms;
 405
 406   gcc_assert (!dst->popcount);
 407
 408   /* A should be at least as large as DEST, to have a defined source.  */
 409   gcc_assert (a->size >= dst_size);
 410   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 411      only copy the subtrahend into dest.  */
 412   if (b->size < min_size)
 413     min_size = b->size;
 414   for (i = 0; i < min_size; i++)
 415     *dstp++ = *ap++ & (~*bp++);
 416   /* Now fill the rest of dest from A, if B was too short.
 417      This makes sense only when destination and A differ.  */
 418   if (dst != a && i != dst_size)
 419     for (; i < dst_size; i++)
 420       *dstp++ = *ap++;
 421 }
 422
 423 /* Return true if there are any bits set in A are also set in B.
 424    Return false otherwise.  */
 425
 426 bool
 427 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
 428 {
 429   const_sbitmap_ptr ap = a->elms;
 430   const_sbitmap_ptr bp = b->elms;
 431   unsigned int i, n;
 432
 433   n = MIN (a->size, b->size);
 434   for (i = 0; i < n; i++)
 435     if ((*ap++ & *bp++) != 0)
 436       return true;
 437
 438   return false;
 439 }
 440
 441 /* Set DST to be (A and B).
 442    Return nonzero if any change is made.  */
 443
 444 bool
 445 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 446 {
 447   unsigned int i, n = dst->size;
 448   sbitmap_ptr dstp = dst->elms;
 449   const_sbitmap_ptr ap = a->elms;
 450   const_sbitmap_ptr bp = b->elms;
 451   SBITMAP_ELT_TYPE changed = 0;
 452
 453   gcc_assert (!dst->popcount);
 454
 455   for (i = 0; i < n; i++)
 456     {
 457       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 458       changed |= *dstp ^ tmp;
 459       *dstp++ = tmp;
 460     }
 461
 462   return changed != 0;
 463 }
 464
 465 void
 466 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 467 {
 468   unsigned int i, n = dst->size;
 469   sbitmap_ptr dstp = dst->elms;
 470   const_sbitmap_ptr ap = a->elms;
 471   const_sbitmap_ptr bp = b->elms;
 472   bool has_popcount = dst->popcount != NULL;
 473   unsigned char *popcountp = dst->popcount;
 474
 475   for (i = 0; i < n; i++)
 476     {
 477       const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 478       if (has_popcount)
 479         {
 480           bool wordchanged = (*dstp ^ tmp) != 0;
 481           if (wordchanged)
 482             *popcountp = do_popcount (tmp);
 483           popcountp++;
 484         }
 485       *dstp++ = tmp;
 486     }
 487 #ifdef BITMAP_DEBUGGING
 488   if (has_popcount)
 489     sbitmap_verify_popcount (dst);
 490 #endif
 491 }
 492
 493 /* Set DST to be (A xor B)).
 494    Return nonzero if any change is made.  */
 495
 496 bool
 497 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 498 {
 499   unsigned int i, n = dst->size;
 500   sbitmap_ptr dstp = dst->elms;
 501   const_sbitmap_ptr ap = a->elms;
 502   const_sbitmap_ptr bp = b->elms;
 503   SBITMAP_ELT_TYPE changed = 0;
 504
 505   gcc_assert (!dst->popcount);
 506
 507   for (i = 0; i < n; i++)
 508     {
 509       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 510       changed |= *dstp ^ tmp;
 511       *dstp++ = tmp;
 512     }
 513
 514   return changed != 0;
 515 }
 516
 517 void
 518 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 519 {
 520   unsigned int i, n = dst->size;
 521   sbitmap_ptr dstp = dst->elms;
 522   const_sbitmap_ptr ap = a->elms;
 523   const_sbitmap_ptr bp = b->elms;
 524   bool has_popcount = dst->popcount != NULL;
 525   unsigned char *popcountp = dst->popcount;
 526
 527   for (i = 0; i < n; i++)
 528     {
 529       const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 530       if (has_popcount)
 531         {
 532           bool wordchanged = (*dstp ^ tmp) != 0;
 533           if (wordchanged)
 534             *popcountp = do_popcount (tmp);
 535           popcountp++;
 536         }
 537       *dstp++ = tmp;
 538     }
 539 #ifdef BITMAP_DEBUGGING
 540   if (has_popcount)
 541     sbitmap_verify_popcount (dst);
 542 #endif
 543 }
 544
 545 /* Set DST to be (A or B)).
 546    Return nonzero if any change is made.  */
 547
 548 bool
 549 sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
 550 {
 551   unsigned int i, n = dst->size;
 552   sbitmap_ptr dstp = dst->elms;
 553   const_sbitmap_ptr ap = a->elms;
 554   const_sbitmap_ptr bp = b->elms;
 555   SBITMAP_ELT_TYPE changed = 0;
 556
 557   gcc_assert (!dst->popcount);
 558
 559   for (i = 0; i < n; i++)
 560     {
 561       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 562       changed |= *dstp ^ tmp;
 563       *dstp++ = tmp;
 564     }
 565
 566   return changed != 0;
 567 }
 568
 569 void
 570 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
 571 {
 572   unsigned int i, n = dst->size;
 573   sbitmap_ptr dstp = dst->elms;
 574   const_sbitmap_ptr ap = a->elms;
 575   const_sbitmap_ptr bp = b->elms;
 576   bool has_popcount = dst->popcount != NULL;
 577   unsigned char *popcountp = dst->popcount;
 578
 579   for (i = 0; i < n; i++)
 580     {
 581       const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 582       if (has_popcount)
 583         {
 584           bool wordchanged = (*dstp ^ tmp) != 0;
 585           if (wordchanged)
 586             *popcountp = do_popcount (tmp);
 587           popcountp++;
 588         }
 589       *dstp++ = tmp;
 590     }
 591 #ifdef BITMAP_DEBUGGING
 592   if (has_popcount)
 593     sbitmap_verify_popcount (dst);
 594 #endif
 595 }
 596
 597 /* Return nonzero if A is a subset of B.  */
 598
 599 bool
 600 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
 601 {
 602   unsigned int i, n = a->size;
 603   const_sbitmap_ptr ap, bp;
 604
 605   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 606     if ((*ap | *bp) != *bp)
 607       return false;
 608
 609   return true;
 610 }
 611
 612 /* Set DST to be (A or (B and C)).
 613    Return nonzero if any change is made.  */
 614
 615 bool
 616 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 617 {
 618   unsigned int i, n = dst->size;
 619   sbitmap_ptr dstp = dst->elms;
 620   const_sbitmap_ptr ap = a->elms;
 621   const_sbitmap_ptr bp = b->elms;
 622   const_sbitmap_ptr cp = c->elms;
 623   SBITMAP_ELT_TYPE changed = 0;
 624
 625   gcc_assert (!dst->popcount);
 626
 627   for (i = 0; i < n; i++)
 628     {
 629       const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 630       changed |= *dstp ^ tmp;
 631       *dstp++ = tmp;
 632     }
 633
 634   return changed != 0;
 635 }
 636
 637 void
 638 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 639 {
 640   unsigned int i, n = dst->size;
 641   sbitmap_ptr dstp = dst->elms;
 642   const_sbitmap_ptr ap = a->elms;
 643   const_sbitmap_ptr bp = b->elms;
 644   const_sbitmap_ptr cp = c->elms;
 645
 646   gcc_assert (!dst->popcount);
 647
 648   for (i = 0; i < n; i++)
 649     *dstp++ = *ap++ | (*bp++ & *cp++);
 650 }
 651
 652 /* Set DST to be (A and (B or C)).
 653    Return nonzero if any change is made.  */
 654
 655 bool
 656 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 657 {
 658   unsigned int i, n = dst->size;
 659   sbitmap_ptr dstp = dst->elms;
 660   const_sbitmap_ptr ap = a->elms;
 661   const_sbitmap_ptr bp = b->elms;
 662   const_sbitmap_ptr cp = c->elms;
 663   SBITMAP_ELT_TYPE changed = 0;
 664
 665   gcc_assert (!dst->popcount);
 666
 667   for (i = 0; i < n; i++)
 668     {
 669       const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 670       changed |= *dstp ^ tmp;
 671       *dstp++ = tmp;
 672     }
 673
 674   return changed != 0;
 675 }
 676
 677 void
 678 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
 679 {
 680   unsigned int i, n = dst->size;
 681   sbitmap_ptr dstp = dst->elms;
 682   const_sbitmap_ptr ap = a->elms;
 683   const_sbitmap_ptr bp = b->elms;
 684   const_sbitmap_ptr cp = c->elms;
 685
 686   for (i = 0; i < n; i++)
 687     *dstp++ = *ap++ & (*bp++ | *cp++);
 688 }
 689
 690 #ifdef IN_GCC
 691 /* Set the bitmap DST to the intersection of SRC of successors of
 692    block number BB, using the new flow graph structures.  */
 693
 694 void
 695 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
 696 {
 697   basic_block b = BASIC_BLOCK (bb);
 698   unsigned int set_size = dst->size;
 699   edge e;
 700   unsigned ix;
 701
 702   gcc_assert (!dst->popcount);
 703
 704   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 705     {
 706       e = EDGE_SUCC (b, ix);
 707       if (e->dest == EXIT_BLOCK_PTR)
 708         continue;
 709
 710       sbitmap_copy (dst, src[e->dest->index]);
 711       break;
 712     }
 713
 714   if (e == 0)
 715     sbitmap_ones (dst);
 716   else
 717     for (++ix; ix < EDGE_COUNT (b->succs); ix++)
 718       {
 719         unsigned int i;
 720         sbitmap_ptr p, r;
 721
 722         e = EDGE_SUCC (b, ix);
 723         if (e->dest == EXIT_BLOCK_PTR)
 724           continue;
 725
 726         p = src[e->dest->index]->elms;
 727         r = dst->elms;
 728         for (i = 0; i < set_size; i++)
 729           *r++ &= *p++;
 730       }
 731 }
 732
 733 /* Set the bitmap DST to the intersection of SRC of predecessors of
 734    block number BB, using the new flow graph structures.  */
 735
 736 void
 737 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
 738 {
 739   basic_block b = BASIC_BLOCK (bb);
 740   unsigned int set_size = dst->size;
 741   edge e;
 742   unsigned ix;
 743
 744   gcc_assert (!dst->popcount);
 745
 746   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 747     {
 748       e = EDGE_PRED (b, ix);
 749       if (e->src == ENTRY_BLOCK_PTR)
 750         continue;
 751
 752       sbitmap_copy (dst, src[e->src->index]);
 753       break;
 754     }
 755
 756   if (e == 0)
 757     sbitmap_ones (dst);
 758   else
 759     for (++ix; ix < EDGE_COUNT (b->preds); ix++)
 760       {
 761         unsigned int i;
 762         sbitmap_ptr p, r;
 763
 764         e = EDGE_PRED (b, ix);
 765         if (e->src == ENTRY_BLOCK_PTR)
 766           continue;
 767
 768         p = src[e->src->index]->elms;
 769         r = dst->elms;
 770         for (i = 0; i < set_size; i++)
 771           *r++ &= *p++;
 772       }
 773 }
 774
 775 /* Set the bitmap DST to the union of SRC of successors of
 776    block number BB, using the new flow graph structures.  */
 777
 778 void
 779 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
 780 {
 781   basic_block b = BASIC_BLOCK (bb);
 782   unsigned int set_size = dst->size;
 783   edge e;
 784   unsigned ix;
 785
 786   gcc_assert (!dst->popcount);
 787
 788   for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 789     {
 790       e = EDGE_SUCC (b, ix);
 791       if (e->dest == EXIT_BLOCK_PTR)
 792         continue;
 793
 794       sbitmap_copy (dst, src[e->dest->index]);
 795       break;
 796     }
 797
 798   if (ix == EDGE_COUNT (b->succs))
 799     sbitmap_zero (dst);
 800   else
 801     for (ix++; ix < EDGE_COUNT (b->succs); ix++)
 802       {
 803         unsigned int i;
 804         sbitmap_ptr p, r;
 805
 806         e = EDGE_SUCC (b, ix);
 807         if (e->dest == EXIT_BLOCK_PTR)
 808           continue;
 809
 810         p = src[e->dest->index]->elms;
 811         r = dst->elms;
 812         for (i = 0; i < set_size; i++)
 813           *r++ |= *p++;
 814       }
 815 }
 816
 817 /* Set the bitmap DST to the union of SRC of predecessors of
 818    block number BB, using the new flow graph structures.  */
 819
 820 void
 821 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
 822 {
 823   basic_block b = BASIC_BLOCK (bb);
 824   unsigned int set_size = dst->size;
 825   edge e;
 826   unsigned ix;
 827
 828   gcc_assert (!dst->popcount);
 829
 830   for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 831     {
 832       e = EDGE_PRED (b, ix);
 833       if (e->src== ENTRY_BLOCK_PTR)
 834         continue;
 835
 836       sbitmap_copy (dst, src[e->src->index]);
 837       break;
 838     }
 839
 840   if (ix == EDGE_COUNT (b->preds))
 841     sbitmap_zero (dst);
 842   else
 843     for (ix++; ix < EDGE_COUNT (b->preds); ix++)
 844       {
 845         unsigned int i;
 846         sbitmap_ptr p, r;
 847
 848         e = EDGE_PRED (b, ix);
 849         if (e->src == ENTRY_BLOCK_PTR)
 850           continue;
 851
 852         p = src[e->src->index]->elms;
 853         r = dst->elms;
 854         for (i = 0; i < set_size; i++)
 855           *r++ |= *p++;
 856       }
 857 }
 858 #endif
 859
 860 /* Return number of first bit set in the bitmap, -1 if none.  */
 861
 862 int
 863 sbitmap_first_set_bit (const_sbitmap bmap)
 864 {
 865   unsigned int n = 0;
 866   sbitmap_iterator sbi;
 867
 868   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
 869     return n;
 870   return -1;
 871 }
 872
 873 /* Return number of last bit set in the bitmap, -1 if none.  */
 874
 875 int
 876 sbitmap_last_set_bit (const_sbitmap bmap)
 877 {
 878   int i;
 879   const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
 880
 881   for (i = bmap->size - 1; i >= 0; i--)
 882     {
 883       const SBITMAP_ELT_TYPE word = ptr[i];
 884
 885       if (word != 0)
 886         {
 887           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 888           SBITMAP_ELT_TYPE mask
 889             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 890
 891           while (1)
 892             {
 893               if ((word & mask) != 0)
 894                 return index;
 895
 896               mask >>= 1;
 897               index--;
 898             }
 899         }
 900     }
 901
 902   return -1;
 903 }
 904
 905 void
 906 dump_sbitmap (FILE *file, const_sbitmap bmap)
 907 {
 908   unsigned int i, n, j;
 909   unsigned int set_size = bmap->size;
 910   unsigned int total_bits = bmap->n_bits;
 911
 912   fprintf (file, "  ");
 913   for (i = n = 0; i < set_size && n < total_bits; i++)
 914     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 915       {
 916         if (n != 0 && n % 10 == 0)
 917           fprintf (file, " ");
 918
 919         fprintf (file, "%d",
 920                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 921       }
 922
 923   fprintf (file, "\n");
 924 }
 925
 926 void
 927 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
 928 {
 929   unsigned int i, pos;
 930
 931   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 932
 933   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 934     if (TEST_BIT (bmap, i))
 935       {
 936         if (pos > 70)
 937           {
 938             fprintf (file, "\n  ");
 939             pos = 0;
 940           }
 941
 942         fprintf (file, "%d ", i);
 943         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 944       }
 945
 946   fprintf (file, "}\n");
 947 }
 948
 949 void
 950 debug_sbitmap (const_sbitmap bmap)
 951 {
 952   dump_sbitmap_file (stderr, bmap);
 953 }
 954
 955 void
 956 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
 957                      sbitmap *bmaps, int n_maps)
 958 {
 959   int bb;
 960
 961   fprintf (file, "%s\n", title);
 962   for (bb = 0; bb < n_maps; bb++)
 963     {
 964       fprintf (file, "%s %d\n", subtitle, bb);
 965       dump_sbitmap (file, bmaps[bb]);
 966     }
 967
 968   fprintf (file, "\n");
 969 }
 970
 971 #if GCC_VERSION < 3400
 972 /* Table of number of set bits in a character, indexed by value of char.  */
 973 static const unsigned char popcount_table[] =
 974 {
 975     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,
 976     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,
 977     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,
 978     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,
 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     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,
 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     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,
 983 };
 984
 985 /* Count the bits in an SBITMAP element A.  */
 986
 987 static unsigned long
 988 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
 989 {
 990   unsigned long ret = 0;
 991   unsigned i;
 992
 993   if (a == 0)
 994     return 0;
 995
 996   /* Just do this the table way for now  */
 997   for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
 998     ret += popcount_table[(a >> i) & 0xff];
 999   return ret;
1000 }
1001 #endif
1002
1003 /* Count the number of bits in SBITMAP a, up to bit MAXBIT.  */
1004
1005 unsigned long
1006 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
1007 {
1008   unsigned long count = 0;
1009   unsigned ix;
1010   unsigned int lastword;
1011
1012   if (maxbit == 0)
1013     return 0;
1014
1015   if (maxbit >= a->n_bits)
1016     maxbit = a->n_bits;
1017
1018   /* Count the bits in the full word.  */
1019   lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1020   for (ix = 0; ix < lastword; ix++)
1021     {
1022       if (a->popcount)
1023         {
1024           count += a->popcount[ix];
1025 #ifdef BITMAP_DEBUGGING
1026           gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1027 #endif
1028         }
1029       else
1030         count += do_popcount (a->elms[ix]);
1031     }
1032
1033   /* Count the remaining bits.  */
1034   if (lastword < a->size)
1035     {
1036       unsigned int bitindex;
1037       SBITMAP_ELT_TYPE theword = a->elms[lastword];
1038
1039       bitindex = maxbit % SBITMAP_ELT_BITS;
1040       if (bitindex != 0)
1041         {
1042           theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1043           count += do_popcount (theword);
1044         }
1045     }
1046   return count;
1047 }
1048