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