2 Copyright (C) 1999, 2000, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
29 #include "basic-block.h"
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)
37 #error "internal error: sbitmap.h and hwint.h are inconsistent"
40 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
41 #define do_popcount(x) sbitmap_elt_popcount((x))
44 /* This macro controls debugging that is as expensive as the
45 operations it verifies. */
47 /* #define BITMAP_DEBUGGING */
48 #ifdef BITMAP_DEBUGGING
50 /* Verify the population count of sbitmap A matches the cached value,
51 if there is a cached value. */
54 sbitmap_verify_popcount (sbitmap a)
57 unsigned int lastword;
63 for (ix = 0; ix < lastword; ix++)
64 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
68 /* Bitmap manipulation routines. */
70 /* Allocate a simple bitmap of N_ELMS bits. */
73 sbitmap_alloc (unsigned int n_elms)
75 unsigned int bytes, size, amt;
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));
83 bmap->n_bits = n_elms;
85 bmap->popcount = NULL;
89 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */
92 sbitmap_alloc_with_popcount (unsigned int n_elms)
96 bmap = sbitmap_alloc (n_elms);
97 bmap->popcount = xmalloc (bmap->size * sizeof (unsigned char));
101 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
102 size of BMAP, clear the new bits to zero if the DEF argument
103 is zero, and set them to one otherwise. */
106 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
108 unsigned int bytes, size, amt;
109 unsigned int last_bit;
111 size = SBITMAP_SET_SIZE (n_elms);
112 bytes = size * sizeof (SBITMAP_ELT_TYPE);
113 if (bytes > SBITMAP_SIZE_BYTES (bmap))
115 amt = (sizeof (struct simple_bitmap_def)
116 + bytes - sizeof (SBITMAP_ELT_TYPE));
117 bmap = xrealloc (bmap, amt);
119 bmap->popcount = xrealloc (bmap->popcount,
120 size * sizeof (unsigned char));
123 if (n_elms > bmap->n_bits)
127 memset (bmap->elms + bmap->size, -1,
128 bytes - SBITMAP_SIZE_BYTES (bmap));
130 /* Set the new bits if the original last element. */
131 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
133 bmap->elms[bmap->size - 1]
134 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
136 /* Clear the unused bit in the new last element. */
137 last_bit = n_elms % SBITMAP_ELT_BITS;
140 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
144 memset (bmap->elms + bmap->size, 0,
145 bytes - SBITMAP_SIZE_BYTES (bmap));
147 memset (bmap->popcount + bmap->size, 0,
148 (size * sizeof (unsigned char))
149 - (bmap->size * sizeof (unsigned char)));
153 else if (n_elms < bmap->n_bits)
155 /* Clear the surplus bits in the last word. */
156 last_bit = n_elms % SBITMAP_ELT_BITS;
160 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
162 bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
166 bmap->n_bits = n_elms;
171 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
174 sbitmap_realloc (sbitmap src, unsigned int n_elms)
176 unsigned int bytes, size, amt;
179 size = SBITMAP_SET_SIZE (n_elms);
180 bytes = size * sizeof (SBITMAP_ELT_TYPE);
181 amt = (sizeof (struct simple_bitmap_def)
182 + bytes - sizeof (SBITMAP_ELT_TYPE));
184 if (SBITMAP_SIZE_BYTES (src) >= bytes)
186 src->n_bits = n_elms;
190 bmap = (sbitmap) xrealloc (src, amt);
191 bmap->n_bits = n_elms;
196 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
199 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
201 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
202 sbitmap *bitmap_vector;
204 size = SBITMAP_SET_SIZE (n_elms);
205 bytes = size * sizeof (SBITMAP_ELT_TYPE);
206 elm_bytes = (sizeof (struct simple_bitmap_def)
207 + bytes - sizeof (SBITMAP_ELT_TYPE));
208 vector_bytes = n_vecs * sizeof (sbitmap *);
210 /* Round up `vector_bytes' to account for the alignment requirements
211 of an sbitmap. One could allocate the vector-table and set of sbitmaps
212 separately, but that requires maintaining two pointers or creating
213 a cover struct to hold both pointers (so our result is still just
214 one pointer). Neither is a bad idea, but this is simpler for now. */
216 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
217 struct { char x; SBITMAP_ELT_TYPE y; } align;
218 int alignment = (char *) & align.y - & align.x;
219 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
222 amt = vector_bytes + (n_vecs * elm_bytes);
223 bitmap_vector = xmalloc (amt);
225 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
227 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
229 bitmap_vector[i] = b;
235 return bitmap_vector;
238 /* Copy sbitmap SRC to DST. */
241 sbitmap_copy (sbitmap dst, sbitmap src)
243 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
245 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
248 /* Copy the first N elements of sbitmap SRC to DST. */
251 sbitmap_copy_n (sbitmap dst, sbitmap src, unsigned int n)
253 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
255 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
258 /* Determine if a == b. */
260 sbitmap_equal (sbitmap a, sbitmap b)
262 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
265 /* Zero all elements in a bitmap. */
268 sbitmap_zero (sbitmap bmap)
270 memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
272 memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
275 /* Set all elements in a bitmap to ones. */
278 sbitmap_ones (sbitmap bmap)
280 unsigned int last_bit;
282 memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
284 memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
286 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
289 bmap->elms[bmap->size - 1]
290 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
292 bmap->popcount[bmap->size - 1]
293 = do_popcount (bmap->elms[bmap->size - 1]);
297 /* Zero a vector of N_VECS bitmaps. */
300 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
304 for (i = 0; i < n_vecs; i++)
305 sbitmap_zero (bmap[i]);
308 /* Set a vector of N_VECS bitmaps to ones. */
311 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
315 for (i = 0; i < n_vecs; i++)
316 sbitmap_ones (bmap[i]);
319 /* Set DST to be A union (B - C).
321 Returns true if any change is made. */
324 sbitmap_union_of_diff_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
326 unsigned int i, n = dst->size;
327 sbitmap_ptr dstp = dst->elms;
328 sbitmap_ptr ap = a->elms;
329 sbitmap_ptr bp = b->elms;
330 sbitmap_ptr cp = c->elms;
331 SBITMAP_ELT_TYPE changed = 0;
333 gcc_assert (!dst->popcount);
335 for (i = 0; i < n; i++)
337 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
338 changed |= *dstp ^ tmp;
346 sbitmap_union_of_diff (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
348 unsigned int i, n = dst->size;
349 sbitmap_ptr dstp = dst->elms;
350 sbitmap_ptr ap = a->elms;
351 sbitmap_ptr bp = b->elms;
352 sbitmap_ptr cp = c->elms;
354 gcc_assert (!dst->popcount && !a->popcount
355 && !b->popcount && !c->popcount);
357 for (i = 0; i < n; i++)
358 *dstp++ = *ap++ | (*bp++ & ~*cp++);
361 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
364 sbitmap_not (sbitmap dst, sbitmap src)
366 unsigned int i, n = dst->size;
367 sbitmap_ptr dstp = dst->elms;
368 sbitmap_ptr srcp = src->elms;
369 unsigned int last_bit;
371 gcc_assert (!dst->popcount);
373 for (i = 0; i < n; i++)
376 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */
377 last_bit = src->n_bits % SBITMAP_ELT_BITS;
379 dst->elms[n-1] = dst->elms[n-1]
380 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
383 /* Set the bits in DST to be the difference between the bits
384 in A and the bits in B. i.e. dst = a & (~b). */
387 sbitmap_difference (sbitmap dst, sbitmap a, sbitmap b)
389 unsigned int i, dst_size = dst->size;
390 unsigned int min_size = dst->size;
391 sbitmap_ptr dstp = dst->elms;
392 sbitmap_ptr ap = a->elms;
393 sbitmap_ptr bp = b->elms;
395 gcc_assert (!dst->popcount);
397 /* A should be at least as large as DEST, to have a defined source. */
398 gcc_assert (a->size >= dst_size);
399 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
400 only copy the subtrahend into dest. */
401 if (b->size < min_size)
403 for (i = 0; i < min_size; i++)
404 *dstp++ = *ap++ & (~*bp++);
405 /* Now fill the rest of dest from A, if B was too short.
406 This makes sense only when destination and A differ. */
407 if (dst != a && i != dst_size)
408 for (; i < dst_size; i++)
412 /* Return true if there are any bits set in A are also set in B.
413 Return false otherwise. */
416 sbitmap_any_common_bits (sbitmap a, sbitmap b)
418 sbitmap_ptr ap = a->elms;
419 sbitmap_ptr bp = b->elms;
422 n = MIN (a->size, b->size);
423 for (i = 0; i < n; i++)
424 if ((*ap++ & *bp++) != 0)
430 /* Set DST to be (A and B).
431 Return nonzero if any change is made. */
434 sbitmap_a_and_b_cg (sbitmap dst, sbitmap a, sbitmap b)
436 unsigned int i, n = dst->size;
437 sbitmap_ptr dstp = dst->elms;
438 sbitmap_ptr ap = a->elms;
439 sbitmap_ptr bp = b->elms;
440 SBITMAP_ELT_TYPE changed = 0;
442 gcc_assert (!dst->popcount);
444 for (i = 0; i < n; i++)
446 SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
447 changed |= *dstp ^ tmp;
455 sbitmap_a_and_b (sbitmap dst, sbitmap a, sbitmap b)
457 unsigned int i, n = dst->size;
458 sbitmap_ptr dstp = dst->elms;
459 sbitmap_ptr ap = a->elms;
460 sbitmap_ptr bp = b->elms;
461 bool has_popcount = dst->popcount != NULL;
462 unsigned char *popcountp = dst->popcount;
464 for (i = 0; i < n; i++)
466 SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
469 bool wordchanged = (*dstp ^ tmp) != 0;
471 *popcountp = do_popcount (tmp);
476 #ifdef BITMAP_DEBUGGING
478 sbitmap_verify_popcount (dst);
482 /* Set DST to be (A xor B)).
483 Return nonzero if any change is made. */
486 sbitmap_a_xor_b_cg (sbitmap dst, sbitmap a, sbitmap b)
488 unsigned int i, n = dst->size;
489 sbitmap_ptr dstp = dst->elms;
490 sbitmap_ptr ap = a->elms;
491 sbitmap_ptr bp = b->elms;
492 SBITMAP_ELT_TYPE changed = 0;
494 gcc_assert (!dst->popcount);
496 for (i = 0; i < n; i++)
498 SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
499 changed |= *dstp ^ tmp;
507 sbitmap_a_xor_b (sbitmap dst, sbitmap a, sbitmap b)
509 unsigned int i, n = dst->size;
510 sbitmap_ptr dstp = dst->elms;
511 sbitmap_ptr ap = a->elms;
512 sbitmap_ptr bp = b->elms;
513 bool has_popcount = dst->popcount != NULL;
514 unsigned char *popcountp = dst->popcount;
516 for (i = 0; i < n; i++)
518 SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
521 bool wordchanged = (*dstp ^ tmp) != 0;
523 *popcountp = do_popcount (tmp);
528 #ifdef BITMAP_DEBUGGING
530 sbitmap_verify_popcount (dst);
534 /* Set DST to be (A or B)).
535 Return nonzero if any change is made. */
538 sbitmap_a_or_b_cg (sbitmap dst, sbitmap a, sbitmap b)
540 unsigned int i, n = dst->size;
541 sbitmap_ptr dstp = dst->elms;
542 sbitmap_ptr ap = a->elms;
543 sbitmap_ptr bp = b->elms;
544 SBITMAP_ELT_TYPE changed = 0;
546 gcc_assert (!dst->popcount);
548 for (i = 0; i < n; i++)
550 SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
551 changed |= *dstp ^ tmp;
559 sbitmap_a_or_b (sbitmap dst, sbitmap a, sbitmap b)
561 unsigned int i, n = dst->size;
562 sbitmap_ptr dstp = dst->elms;
563 sbitmap_ptr ap = a->elms;
564 sbitmap_ptr bp = b->elms;
565 bool has_popcount = dst->popcount != NULL;
566 unsigned char *popcountp = dst->popcount;
568 for (i = 0; i < n; i++)
570 SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
573 bool wordchanged = (*dstp ^ tmp) != 0;
575 *popcountp = do_popcount (tmp);
580 #ifdef BITMAP_DEBUGGING
582 sbitmap_verify_popcount (dst);
586 /* Return nonzero if A is a subset of B. */
589 sbitmap_a_subset_b_p (sbitmap a, sbitmap b)
591 unsigned int i, n = a->size;
594 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
595 if ((*ap | *bp) != *bp)
601 /* Set DST to be (A or (B and C)).
602 Return nonzero if any change is made. */
605 sbitmap_a_or_b_and_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
607 unsigned int i, n = dst->size;
608 sbitmap_ptr dstp = dst->elms;
609 sbitmap_ptr ap = a->elms;
610 sbitmap_ptr bp = b->elms;
611 sbitmap_ptr cp = c->elms;
612 SBITMAP_ELT_TYPE changed = 0;
614 gcc_assert (!dst->popcount);
616 for (i = 0; i < n; i++)
618 SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
619 changed |= *dstp ^ tmp;
627 sbitmap_a_or_b_and_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
629 unsigned int i, n = dst->size;
630 sbitmap_ptr dstp = dst->elms;
631 sbitmap_ptr ap = a->elms;
632 sbitmap_ptr bp = b->elms;
633 sbitmap_ptr cp = c->elms;
635 gcc_assert (!dst->popcount);
637 for (i = 0; i < n; i++)
638 *dstp++ = *ap++ | (*bp++ & *cp++);
641 /* Set DST to be (A and (B or C)).
642 Return nonzero if any change is made. */
645 sbitmap_a_and_b_or_c_cg (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
647 unsigned int i, n = dst->size;
648 sbitmap_ptr dstp = dst->elms;
649 sbitmap_ptr ap = a->elms;
650 sbitmap_ptr bp = b->elms;
651 sbitmap_ptr cp = c->elms;
652 SBITMAP_ELT_TYPE changed = 0;
654 gcc_assert (!dst->popcount);
656 for (i = 0; i < n; i++)
658 SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
659 changed |= *dstp ^ tmp;
667 sbitmap_a_and_b_or_c (sbitmap dst, sbitmap a, sbitmap b, sbitmap c)
669 unsigned int i, n = dst->size;
670 sbitmap_ptr dstp = dst->elms;
671 sbitmap_ptr ap = a->elms;
672 sbitmap_ptr bp = b->elms;
673 sbitmap_ptr cp = c->elms;
675 for (i = 0; i < n; i++)
676 *dstp++ = *ap++ & (*bp++ | *cp++);
680 /* Set the bitmap DST to the intersection of SRC of successors of
681 block number BB, using the new flow graph structures. */
684 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
686 basic_block b = BASIC_BLOCK (bb);
687 unsigned int set_size = dst->size;
691 gcc_assert (!dst->popcount);
693 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
695 e = EDGE_SUCC (b, ix);
696 if (e->dest == EXIT_BLOCK_PTR)
699 sbitmap_copy (dst, src[e->dest->index]);
706 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
711 e = EDGE_SUCC (b, ix);
712 if (e->dest == EXIT_BLOCK_PTR)
715 p = src[e->dest->index]->elms;
717 for (i = 0; i < set_size; i++)
722 /* Set the bitmap DST to the intersection of SRC of predecessors of
723 block number BB, using the new flow graph structures. */
726 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
728 basic_block b = BASIC_BLOCK (bb);
729 unsigned int set_size = dst->size;
733 gcc_assert (!dst->popcount);
735 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
737 e = EDGE_PRED (b, ix);
738 if (e->src == ENTRY_BLOCK_PTR)
741 sbitmap_copy (dst, src[e->src->index]);
748 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
753 e = EDGE_PRED (b, ix);
754 if (e->src == ENTRY_BLOCK_PTR)
757 p = src[e->src->index]->elms;
759 for (i = 0; i < set_size; i++)
764 /* Set the bitmap DST to the union of SRC of successors of
765 block number BB, using the new flow graph structures. */
768 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
770 basic_block b = BASIC_BLOCK (bb);
771 unsigned int set_size = dst->size;
775 gcc_assert (!dst->popcount);
777 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
779 e = EDGE_SUCC (b, ix);
780 if (e->dest == EXIT_BLOCK_PTR)
783 sbitmap_copy (dst, src[e->dest->index]);
787 if (ix == EDGE_COUNT (b->succs))
790 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
795 e = EDGE_SUCC (b, ix);
796 if (e->dest == EXIT_BLOCK_PTR)
799 p = src[e->dest->index]->elms;
801 for (i = 0; i < set_size; i++)
806 /* Set the bitmap DST to the union of SRC of predecessors of
807 block number BB, using the new flow graph structures. */
810 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
812 basic_block b = BASIC_BLOCK (bb);
813 unsigned int set_size = dst->size;
817 gcc_assert (!dst->popcount);
819 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
821 e = EDGE_PRED (b, ix);
822 if (e->src== ENTRY_BLOCK_PTR)
825 sbitmap_copy (dst, src[e->src->index]);
829 if (ix == EDGE_COUNT (b->preds))
832 for (ix++; ix < EDGE_COUNT (b->preds); ix++)
837 e = EDGE_PRED (b, ix);
838 if (e->src == ENTRY_BLOCK_PTR)
841 p = src[e->src->index]->elms;
843 for (i = 0; i < set_size; i++)
849 /* Return number of first bit set in the bitmap, -1 if none. */
852 sbitmap_first_set_bit (sbitmap bmap)
855 sbitmap_iterator sbi;
857 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
862 /* Return number of last bit set in the bitmap, -1 if none. */
865 sbitmap_last_set_bit (sbitmap bmap)
868 SBITMAP_ELT_TYPE *ptr = bmap->elms;
870 for (i = bmap->size - 1; i >= 0; i--)
872 SBITMAP_ELT_TYPE word = ptr[i];
876 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
877 SBITMAP_ELT_TYPE mask
878 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
882 if ((word & mask) != 0)
895 dump_sbitmap (FILE *file, sbitmap bmap)
897 unsigned int i, n, j;
898 unsigned int set_size = bmap->size;
899 unsigned int total_bits = bmap->n_bits;
902 for (i = n = 0; i < set_size && n < total_bits; i++)
903 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
905 if (n != 0 && n % 10 == 0)
909 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
912 fprintf (file, "\n");
916 dump_sbitmap_file (FILE *file, sbitmap bmap)
920 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
922 for (pos = 30, i = 0; i < bmap->n_bits; i++)
923 if (TEST_BIT (bmap, i))
927 fprintf (file, "\n ");
931 fprintf (file, "%d ", i);
932 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
935 fprintf (file, "}\n");
939 debug_sbitmap (sbitmap bmap)
941 dump_sbitmap_file (stderr, bmap);
945 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
946 sbitmap *bmaps, int n_maps)
950 fprintf (file, "%s\n", title);
951 for (bb = 0; bb < n_maps; bb++)
953 fprintf (file, "%s %d\n", subtitle, bb);
954 dump_sbitmap (file, bmaps[bb]);
957 fprintf (file, "\n");
960 #if GCC_VERSION < 3400
961 /* Table of number of set bits in a character, indexed by value of char. */
962 static unsigned char popcount_table[] =
964 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
965 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
966 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
967 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
968 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
969 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
970 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
971 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
974 /* Count the bits in an SBITMAP element A. */
977 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
979 unsigned long ret = 0;
985 /* Just do this the table way for now */
986 for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
987 ret += popcount_table[(a >> i) & 0xff];
992 /* Count the number of bits in SBITMAP a, up to bit MAXBIT. */
995 sbitmap_popcount (sbitmap a, unsigned long maxbit)
997 unsigned long count = 0;
999 unsigned int lastword;
1004 if (maxbit >= a->n_bits)
1007 /* Count the bits in the full word. */
1008 lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1009 for (ix = 0; ix < lastword; ix++)
1013 count += a->popcount[ix];
1014 #ifdef BITMAP_DEBUGGING
1015 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1019 count += do_popcount (a->elms[ix]);
1022 /* Count the remaining bits. */
1023 if (lastword < a->size)
1025 unsigned int bitindex;
1026 SBITMAP_ELT_TYPE theword = a->elms[lastword];
1028 bitindex = maxbit % SBITMAP_ELT_BITS;
1031 theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1032 count += do_popcount (theword);