gcc/sbitmap.c

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