contrib/gcc-4.1/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 /* Bitmap manipulation routines.  */
  32
  33 /* Allocate a simple bitmap of N_ELMS bits.  */
  34
  35 sbitmap
  36 sbitmap_alloc (unsigned int n_elms)
  37 {
  38   unsigned int bytes, size, amt;
  39   sbitmap bmap;
  40
  41   size = SBITMAP_SET_SIZE (n_elms);
  42   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  43   amt = (sizeof (struct simple_bitmap_def)
  44          + bytes - sizeof (SBITMAP_ELT_TYPE));
  45   bmap = xmalloc (amt);
  46   bmap->n_bits = n_elms;
  47   bmap->size = size;
  48   bmap->bytes = bytes;
  49   return bmap;
  50 }
  51
  52 /* Resize a simple bitmap BMAP to N_ELMS bits.  If increasing the
  53    size of BMAP, clear the new bits to zero if the DEF argument
  54    is zero, and set them to one otherwise.  */
  55
  56 sbitmap
  57 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
  58 {
  59   unsigned int bytes, size, amt;
  60   unsigned int last_bit;
  61
  62   size = SBITMAP_SET_SIZE (n_elms);
  63   bytes = size * sizeof (SBITMAP_ELT_TYPE);
  64   if (bytes > bmap->bytes)
  65     {
  66       amt = (sizeof (struct simple_bitmap_def)
  67             + bytes - sizeof (SBITMAP_ELT_TYPE));
  68       bmap = xrealloc (bmap, amt);
  69     }
  70
  71   if (n_elms > bmap->n_bits)
  72     {
  73       if (def)
  74         {
  75           memset (bmap->elms + bmap->size, -1, bytes - bmap->bytes);
  76
  77           /* Set the new bits if the original last element.  */
  78           last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
  79           if (last_bit)
  80             bmap->elms[bmap->size - 1]
  81               |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
  82
  83           /* Clear the unused bit in the new last element.  */
  84           last_bit = n_elms % SBITMAP_ELT_BITS;
  85           if (last_bit)
  86             bmap->elms[size - 1]
  87               &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
  88         }
  89       else
  90         memset (bmap->elms + bmap->size, 0, bytes - bmap->bytes);
  91     }
  92   else if (n_elms < bmap->n_bits)
  93     {
  94       /* Clear the surplus bits in the last word.  */
  95       last_bit = n_elms % SBITMAP_ELT_BITS;
  96       if (last_bit)
  97         bmap->elms[size - 1]
  98           &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
  99     }
 100
 101   bmap->n_bits = n_elms;
 102   bmap->size = size;
 103   bmap->bytes = bytes;
 104   return bmap;
 105 }
 106
 107 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized.  */
 108
 109 sbitmap
 110 sbitmap_realloc (sbitmap src, unsigned int n_elms)
 111 {
 112   unsigned int bytes, size, amt;
 113   sbitmap bmap;
 114
 115   size = SBITMAP_SET_SIZE (n_elms);
 116   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 117   amt = (sizeof (struct simple_bitmap_def)
 118          + bytes - sizeof (SBITMAP_ELT_TYPE));
 119
 120   if (src->bytes  >= bytes)
 121     {
 122       src->n_bits = n_elms;
 123       return src;
 124     }
 125
 126   bmap = (sbitmap) xrealloc (src, amt);
 127   bmap->n_bits = n_elms;
 128   bmap->size = size;
 129   bmap->bytes = bytes;
 130   return bmap;
 131 }
 132
 133 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits.  */
 134
 135 sbitmap *
 136 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
 137 {
 138   unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
 139   sbitmap *bitmap_vector;
 140
 141   size = SBITMAP_SET_SIZE (n_elms);
 142   bytes = size * sizeof (SBITMAP_ELT_TYPE);
 143   elm_bytes = (sizeof (struct simple_bitmap_def)
 144                + bytes - sizeof (SBITMAP_ELT_TYPE));
 145   vector_bytes = n_vecs * sizeof (sbitmap *);
 146
 147   /* Round up `vector_bytes' to account for the alignment requirements
 148      of an sbitmap.  One could allocate the vector-table and set of sbitmaps
 149      separately, but that requires maintaining two pointers or creating
 150      a cover struct to hold both pointers (so our result is still just
 151      one pointer).  Neither is a bad idea, but this is simpler for now.  */
 152   {
 153     /* Based on DEFAULT_ALIGNMENT computation in obstack.c.  */
 154     struct { char x; SBITMAP_ELT_TYPE y; } align;
 155     int alignment = (char *) & align.y - & align.x;
 156     vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
 157   }
 158
 159   amt = vector_bytes + (n_vecs * elm_bytes);
 160   bitmap_vector = xmalloc (amt);
 161
 162   for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
 163     {
 164       sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
 165
 166       bitmap_vector[i] = b;
 167       b->n_bits = n_elms;
 168       b->size = size;
 169       b->bytes = bytes;
 170     }
 171
 172   return bitmap_vector;
 173 }
 174
 175 /* Copy sbitmap SRC to DST.  */
 176
 177 void
 178 sbitmap_copy (sbitmap dst, sbitmap src)
 179 {
 180   memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
 181 }
 182
 183 /* Determine if a == b.  */
 184 int
 185 sbitmap_equal (sbitmap a, sbitmap b)
 186 {
 187   return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
 188 }
 189
 190 /* Zero all elements in a bitmap.  */
 191
 192 void
 193 sbitmap_zero (sbitmap bmap)
 194 {
 195   memset (bmap->elms, 0, bmap->bytes);
 196 }
 197
 198 /* Set all elements in a bitmap to ones.  */
 199
 200 void
 201 sbitmap_ones (sbitmap bmap)
 202 {
 203   unsigned int last_bit;
 204
 205   memset (bmap->elms, -1, bmap->bytes);
 206
 207   last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
 208   if (last_bit)
 209     bmap->elms[bmap->size - 1]
 210       = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
 211 }
 212
 213 /* Zero a vector of N_VECS bitmaps.  */
 214
 215 void
 216 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
 217 {
 218   unsigned int i;
 219
 220   for (i = 0; i < n_vecs; i++)
 221     sbitmap_zero (bmap[i]);
 222 }
 223
 224 /* Set a vector of N_VECS bitmaps to ones.  */
 225
 226 void
 227 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
 228 {
 229   unsigned int i;
 230
 231   for (i = 0; i < n_vecs; i++)
 232     sbitmap_ones (bmap[i]);
 233 }
 234
 235 /* Set DST to be A union (B - C).
 236    DST = A | (B & ~C).
 237    Returns true if any change is made.  */
 238
 239 bool
 240 sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 241 {
 242   unsigned int i, n = dst->size;
 243   sbitmap_ptr dstp = dst->elms;
 244   sbitmap_ptr ap = a->elms;
 245   sbitmap_ptr bp = b->elms;
 246   sbitmap_ptr cp = c->elms;
 247   SBITMAP_ELT_TYPE changed = 0;
 248
 249   for (i = 0; i < n; i++)
 250     {
 251       SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
 252       changed |= *dstp ^ tmp;
 253       *dstp++ = tmp;
 254     }
 255
 256   return changed != 0;
 257 }
 258
 259 void
 260 sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 261 {
 262   unsigned int i, n = dst->size;
 263   sbitmap_ptr dstp = dst->elms;
 264   sbitmap_ptr ap = a->elms;
 265   sbitmap_ptr bp = b->elms;
 266   sbitmap_ptr cp = c->elms;
 267
 268   for (i = 0; i < n; i++)
 269     *dstp++ = *ap++ | (*bp++ & ~*cp++);
 270 }
 271
 272 /* Set bitmap DST to the bitwise negation of the bitmap SRC.  */
 273
 274 void
 275 sbitmap_not (sbitmap dst, sbitmap src)
 276 {
 277   unsigned int i, n = dst->size;
 278   sbitmap_ptr dstp = dst->elms;
 279   sbitmap_ptr srcp = src->elms;
 280   unsigned int last_bit;
 281
 282   for (i = 0; i < n; i++)
 283     *dstp++ = ~*srcp++;
 284
 285   /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones.  */
 286   last_bit = src->n_bits % SBITMAP_ELT_BITS;
 287   if (last_bit)
 288     dst->elms[n-1] = dst->elms[n-1]
 289       & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
 290 }
 291
 292 /* Set the bits in DST to be the difference between the bits
 293    in A and the bits in B. i.e. dst = a & (~b).  */
 294
 295 void
 296 sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b)
 297 {
 298   unsigned int i, dst_size = dst->size;
 299   unsigned int min_size = dst->size;
 300   sbitmap_ptr dstp = dst->elms;
 301   sbitmap_ptr ap = a->elms;
 302   sbitmap_ptr bp = b->elms;
 303
 304   /* A should be at least as large as DEST, to have a defined source.  */
 305   gcc_assert (a->size >= dst_size);
 306   /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
 307      only copy the subtrahend into dest.  */
 308   if (b->size < min_size)
 309     min_size = b->size;
 310   for (i = 0; i < min_size; i++)
 311     *dstp++ = *ap++ & (~*bp++);
 312   /* Now fill the rest of dest from A, if B was too short.
 313      This makes sense only when destination and A differ.  */
 314   if (dst != a && i != dst_size)
 315     for (; i < dst_size; i++)
 316       *dstp++ = *ap++;
 317 }
 318
 319 /* Return true if there are any bits set in A are also set in B.
 320    Return false otherwise.  */
 321
 322 bool
 323 sbitmap_any_common_bits (sbitmap a, sbitmap b)
 324 {
 325   sbitmap_ptr ap = a->elms;
 326   sbitmap_ptr bp = b->elms;
 327   unsigned int i, n;
 328
 329   n = MIN (a->size, b->size);
 330   for (i = 0; i < n; i++)
 331     if ((*ap++ & *bp++) != 0)
 332       return true;
 333
 334   return false;
 335 }
 336
 337 /* Set DST to be (A and B).
 338    Return nonzero if any change is made.  */
 339
 340 bool
 341 sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b)
 342 {
 343   unsigned int i, n = dst->size;
 344   sbitmap_ptr dstp = dst->elms;
 345   sbitmap_ptr ap = a->elms;
 346   sbitmap_ptr bp = b->elms;
 347   SBITMAP_ELT_TYPE changed = 0;
 348
 349   for (i = 0; i < n; i++)
 350     {
 351       SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
 352       changed |= *dstp ^ tmp;
 353       *dstp++ = tmp;
 354     }
 355
 356   return changed != 0;
 357 }
 358
 359 void
 360 sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b)
 361 {
 362   unsigned int i, n = dst->size;
 363   sbitmap_ptr dstp = dst->elms;
 364   sbitmap_ptr ap = a->elms;
 365   sbitmap_ptr bp = b->elms;
 366
 367   for (i = 0; i < n; i++)
 368     *dstp++ = *ap++ & *bp++;
 369 }
 370
 371 /* Set DST to be (A xor B)).
 372    Return nonzero if any change is made.  */
 373
 374 bool
 375 sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b)
 376 {
 377   unsigned int i, n = dst->size;
 378   sbitmap_ptr dstp = dst->elms;
 379   sbitmap_ptr ap = a->elms;
 380   sbitmap_ptr bp = b->elms;
 381   SBITMAP_ELT_TYPE changed = 0;
 382
 383   for (i = 0; i < n; i++)
 384     {
 385       SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
 386       changed |= *dstp ^ tmp;
 387       *dstp++ = tmp;
 388     }
 389
 390   return changed != 0;
 391 }
 392
 393 void
 394 sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b)
 395 {
 396   unsigned int i, n = dst->size;
 397   sbitmap_ptr dstp = dst->elms;
 398   sbitmap_ptr ap = a->elms;
 399   sbitmap_ptr bp = b->elms;
 400
 401   for (i = 0; i < n; i++)
 402     *dstp++ = *ap++ ^ *bp++;
 403 }
 404
 405 /* Set DST to be (A or B)).
 406    Return nonzero if any change is made.  */
 407
 408 bool
 409 sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b)
 410 {
 411   unsigned int i, n = dst->size;
 412   sbitmap_ptr dstp = dst->elms;
 413   sbitmap_ptr ap = a->elms;
 414   sbitmap_ptr bp = b->elms;
 415   SBITMAP_ELT_TYPE changed = 0;
 416
 417   for (i = 0; i < n; i++)
 418     {
 419       SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
 420       changed |= *dstp ^ tmp;
 421       *dstp++ = tmp;
 422     }
 423
 424   return changed != 0;
 425 }
 426
 427 void
 428 sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b)
 429 {
 430   unsigned int i, n = dst->size;
 431   sbitmap_ptr dstp = dst->elms;
 432   sbitmap_ptr ap = a->elms;
 433   sbitmap_ptr bp = b->elms;
 434
 435   for (i = 0; i < n; i++)
 436     *dstp++ = *ap++ | *bp++;
 437 }
 438
 439 /* Return nonzero if A is a subset of B.  */
 440
 441 bool
 442 sbitmap_a_subset_b_p (sbitmap a, sbitmap b)
 443 {
 444   unsigned int i, n = a->size;
 445   sbitmap_ptr ap, bp;
 446
 447   for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
 448     if ((*ap | *bp) != *bp)
 449       return false;
 450
 451   return true;
 452 }
 453
 454 /* Set DST to be (A or (B and C)).
 455    Return nonzero if any change is made.  */
 456
 457 bool
 458 sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 459 {
 460   unsigned int i, n = dst->size;
 461   sbitmap_ptr dstp = dst->elms;
 462   sbitmap_ptr ap = a->elms;
 463   sbitmap_ptr bp = b->elms;
 464   sbitmap_ptr cp = c->elms;
 465   SBITMAP_ELT_TYPE changed = 0;
 466
 467   for (i = 0; i < n; i++)
 468     {
 469       SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
 470       changed |= *dstp ^ tmp;
 471       *dstp++ = tmp;
 472     }
 473
 474   return changed != 0;
 475 }
 476
 477 void
 478 sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 479 {
 480   unsigned int i, n = dst->size;
 481   sbitmap_ptr dstp = dst->elms;
 482   sbitmap_ptr ap = a->elms;
 483   sbitmap_ptr bp = b->elms;
 484   sbitmap_ptr cp = c->elms;
 485
 486   for (i = 0; i < n; i++)
 487     *dstp++ = *ap++ | (*bp++ & *cp++);
 488 }
 489
 490 /* Set DST to be (A and (B or C)).
 491    Return nonzero if any change is made.  */
 492
 493 bool
 494 sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 495 {
 496   unsigned int i, n = dst->size;
 497   sbitmap_ptr dstp = dst->elms;
 498   sbitmap_ptr ap = a->elms;
 499   sbitmap_ptr bp = b->elms;
 500   sbitmap_ptr cp = c->elms;
 501   SBITMAP_ELT_TYPE changed = 0;
 502
 503   for (i = 0; i < n; i++)
 504     {
 505       SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
 506       changed |= *dstp ^ tmp;
 507       *dstp++ = tmp;
 508     }
 509
 510   return changed != 0;
 511 }
 512
 513 void
 514 sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
 515 {
 516   unsigned int i, n = dst->size;
 517   sbitmap_ptr dstp = dst->elms;
 518   sbitmap_ptr ap = a->elms;
 519   sbitmap_ptr bp = b->elms;
 520   sbitmap_ptr cp = c->elms;
 521
 522   for (i = 0; i < n; i++)
 523     *dstp++ = *ap++ & (*bp++ | *cp++);
 524 }
 525
 526 #ifdef IN_GCC
 527 /* Set the bitmap DST to the intersection of SRC of successors of
 528    block number BB, using the new flow graph structures.  */
 529
 530 void
 531 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
 532 {
 533   basic_block b = BASIC_BLOCK (bb);
 534   unsigned int set_size = dst->size;
 535   edge e;
 536   unsigned ix;
 537
 538   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 539     {
 540       e = EDGE_SUCC (b, ix);
 541       if (e->dest == EXIT_BLOCK_PTR)
 542         continue;
 543
 544       sbitmap_copy (dst, src[e->dest->index]);
 545       break;
 546     }
 547
 548   if (e == 0)
 549     sbitmap_ones (dst);
 550   else
 551     for (++ix; ix < EDGE_COUNT (b->succs); ix++)
 552       {
 553         unsigned int i;
 554         sbitmap_ptr p, r;
 555
 556         e = EDGE_SUCC (b, ix);
 557         if (e->dest == EXIT_BLOCK_PTR)
 558           continue;
 559
 560         p = src[e->dest->index]->elms;
 561         r = dst->elms;
 562         for (i = 0; i < set_size; i++)
 563           *r++ &= *p++;
 564       }
 565 }
 566
 567 /* Set the bitmap DST to the intersection of SRC of predecessors of
 568    block number BB, using the new flow graph structures.  */
 569
 570 void
 571 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
 572 {
 573   basic_block b = BASIC_BLOCK (bb);
 574   unsigned int set_size = dst->size;
 575   edge e;
 576   unsigned ix;
 577
 578   for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 579     {
 580       e = EDGE_PRED (b, ix);
 581       if (e->src == ENTRY_BLOCK_PTR)
 582         continue;
 583
 584       sbitmap_copy (dst, src[e->src->index]);
 585       break;
 586     }
 587
 588   if (e == 0)
 589     sbitmap_ones (dst);
 590   else
 591     for (++ix; ix < EDGE_COUNT (b->preds); ix++)
 592       {
 593         unsigned int i;
 594         sbitmap_ptr p, r;
 595
 596         e = EDGE_PRED (b, ix);
 597         if (e->src == ENTRY_BLOCK_PTR)
 598           continue;
 599
 600         p = src[e->src->index]->elms;
 601         r = dst->elms;
 602         for (i = 0; i < set_size; i++)
 603           *r++ &= *p++;
 604       }
 605 }
 606
 607 /* Set the bitmap DST to the union of SRC of successors of
 608    block number BB, using the new flow graph structures.  */
 609
 610 void
 611 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
 612 {
 613   basic_block b = BASIC_BLOCK (bb);
 614   unsigned int set_size = dst->size;
 615   edge e;
 616   unsigned ix;
 617
 618   for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
 619     {
 620       e = EDGE_SUCC (b, ix);
 621       if (e->dest == EXIT_BLOCK_PTR)
 622         continue;
 623
 624       sbitmap_copy (dst, src[e->dest->index]);
 625       break;
 626     }
 627
 628   if (ix == EDGE_COUNT (b->succs))
 629     sbitmap_zero (dst);
 630   else
 631     for (ix++; ix < EDGE_COUNT (b->succs); ix++)
 632       {
 633         unsigned int i;
 634         sbitmap_ptr p, r;
 635
 636         e = EDGE_SUCC (b, ix);
 637         if (e->dest == EXIT_BLOCK_PTR)
 638           continue;
 639
 640         p = src[e->dest->index]->elms;
 641         r = dst->elms;
 642         for (i = 0; i < set_size; i++)
 643           *r++ |= *p++;
 644       }
 645 }
 646
 647 /* Set the bitmap DST to the union of SRC of predecessors of
 648    block number BB, using the new flow graph structures.  */
 649
 650 void
 651 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
 652 {
 653   basic_block b = BASIC_BLOCK (bb);
 654   unsigned int set_size = dst->size;
 655   edge e;
 656   unsigned ix;
 657
 658   for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
 659     {
 660       e = EDGE_PRED (b, ix);
 661       if (e->src== ENTRY_BLOCK_PTR)
 662         continue;
 663
 664       sbitmap_copy (dst, src[e->src->index]);
 665       break;
 666     }
 667
 668   if (ix == EDGE_COUNT (b->preds))
 669     sbitmap_zero (dst);
 670   else
 671     for (ix++; ix < EDGE_COUNT (b->preds); ix++)
 672       {
 673         unsigned int i;
 674         sbitmap_ptr p, r;
 675
 676         e = EDGE_PRED (b, ix);
 677         if (e->src == ENTRY_BLOCK_PTR)
 678           continue;
 679
 680         p = src[e->src->index]->elms;
 681         r = dst->elms;
 682         for (i = 0; i < set_size; i++)
 683           *r++ |= *p++;
 684       }
 685 }
 686 #endif
 687
 688 /* Return number of first bit set in the bitmap, -1 if none.  */
 689
 690 int
 691 sbitmap_first_set_bit (sbitmap bmap)
 692 {
 693   unsigned int n = 0;
 694   sbitmap_iterator sbi;
 695
 696   EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
 697     return n;
 698   return -1;
 699 }
 700
 701 /* Return number of last bit set in the bitmap, -1 if none.  */
 702
 703 int
 704 sbitmap_last_set_bit (sbitmap bmap)
 705 {
 706   int i;
 707   SBITMAP_ELT_TYPE *ptr = bmap->elms;
 708
 709   for (i = bmap->size - 1; i >= 0; i--)
 710     {
 711       SBITMAP_ELT_TYPE word = ptr[i];
 712
 713       if (word != 0)
 714         {
 715           unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
 716           SBITMAP_ELT_TYPE mask
 717             = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
 718
 719           while (1)
 720             {
 721               if ((word & mask) != 0)
 722                 return index;
 723
 724               mask >>= 1;
 725               index--;
 726             }
 727         }
 728     }
 729
 730   return -1;
 731 }
 732
 733 void
 734 dump_sbitmap (FILE *file, sbitmap bmap)
 735 {
 736   unsigned int i, n, j;
 737   unsigned int set_size = bmap->size;
 738   unsigned int total_bits = bmap->n_bits;
 739
 740   fprintf (file, "  ");
 741   for (i = n = 0; i < set_size && n < total_bits; i++)
 742     for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
 743       {
 744         if (n != 0 && n % 10 == 0)
 745           fprintf (file, " ");
 746
 747         fprintf (file, "%d",
 748                  (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
 749       }
 750
 751   fprintf (file, "\n");
 752 }
 753
 754 void
 755 dump_sbitmap_file (FILE *file, sbitmap bmap)
 756 {
 757   unsigned int i, pos;
 758
 759   fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
 760
 761   for (pos = 30, i = 0; i < bmap->n_bits; i++)
 762     if (TEST_BIT (bmap, i))
 763       {
 764         if (pos > 70)
 765           {
 766             fprintf (file, "\n  ");
 767             pos = 0;
 768           }
 769
 770         fprintf (file, "%d ", i);
 771         pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
 772       }
 773
 774   fprintf (file, "}\n");
 775 }
 776
 777 void
 778 debug_sbitmap (sbitmap bmap)
 779 {
 780   dump_sbitmap_file (stderr, bmap);
 781 }
 782
 783 void
 784 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
 785                      sbitmap *bmaps, int n_maps)
 786 {
 787   int bb;
 788
 789   fprintf (file, "%s\n", title);
 790   for (bb = 0; bb < n_maps; bb++)
 791     {
 792       fprintf (file, "%s %d\n", subtitle, bb);
 793       dump_sbitmap (file, bmaps[bb]);
 794     }
 795
 796   fprintf (file, "\n");
 797 }