Daily bump.
[official-gcc.git] / gcc / sbitmap.c
blobd8b8d6c1ff50c642b302af35c3ce83362e16639d
1 /* Simple bitmaps.
2 Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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.
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.
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/>. */
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"
31 #if GCC_VERSION >= 3400
32 #if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
33 #define do_popcount(x) __builtin_popcountl(x)
34 #elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
35 #define do_popcount(x) __builtin_popcountll(x)
36 #else
37 #error "internal error: sbitmap.h and hwint.h are inconsistent"
38 #endif
39 #else
40 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE);
41 #define do_popcount(x) sbitmap_elt_popcount((x))
42 #endif
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. */
53 void
54 sbitmap_verify_popcount (const_sbitmap a)
56 unsigned ix;
57 unsigned int lastword;
59 if (!a->popcount)
60 return;
62 lastword = a->size;
63 for (ix = 0; ix < lastword; ix++)
64 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
66 #endif
68 /* Bitmap manipulation routines. */
70 /* Allocate a simple bitmap of N_ELMS bits. */
72 sbitmap
73 sbitmap_alloc (unsigned int n_elms)
75 unsigned int bytes, size, amt;
76 sbitmap bmap;
78 size = SBITMAP_SET_SIZE (n_elms);
79 bytes = size * sizeof (SBITMAP_ELT_TYPE);
80 amt = (sizeof (struct simple_bitmap_def)
81 + bytes - sizeof (SBITMAP_ELT_TYPE));
82 bmap = xmalloc (amt);
83 bmap->n_bits = n_elms;
84 bmap->size = size;
85 bmap->popcount = NULL;
86 return bmap;
89 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */
91 sbitmap
92 sbitmap_alloc_with_popcount (unsigned int n_elms)
94 sbitmap const bmap = sbitmap_alloc (n_elms);
95 bmap->popcount = xmalloc (bmap->size * sizeof (unsigned char));
96 return bmap;
99 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
100 size of BMAP, clear the new bits to zero if the DEF argument
101 is zero, and set them to one otherwise. */
103 sbitmap
104 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def)
106 unsigned int bytes, size, amt;
107 unsigned int last_bit;
109 size = SBITMAP_SET_SIZE (n_elms);
110 bytes = size * sizeof (SBITMAP_ELT_TYPE);
111 if (bytes > SBITMAP_SIZE_BYTES (bmap))
113 amt = (sizeof (struct simple_bitmap_def)
114 + bytes - sizeof (SBITMAP_ELT_TYPE));
115 bmap = xrealloc (bmap, amt);
116 if (bmap->popcount)
117 bmap->popcount = xrealloc (bmap->popcount,
118 size * sizeof (unsigned char));
121 if (n_elms > bmap->n_bits)
123 if (def)
125 memset (bmap->elms + bmap->size, -1,
126 bytes - SBITMAP_SIZE_BYTES (bmap));
128 /* Set the new bits if the original last element. */
129 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
130 if (last_bit)
131 bmap->elms[bmap->size - 1]
132 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
134 /* Clear the unused bit in the new last element. */
135 last_bit = n_elms % SBITMAP_ELT_BITS;
136 if (last_bit)
137 bmap->elms[size - 1]
138 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
140 else
142 memset (bmap->elms + bmap->size, 0,
143 bytes - SBITMAP_SIZE_BYTES (bmap));
144 if (bmap->popcount)
145 memset (bmap->popcount + bmap->size, 0,
146 (size * sizeof (unsigned char))
147 - (bmap->size * sizeof (unsigned char)));
151 else if (n_elms < bmap->n_bits)
153 /* Clear the surplus bits in the last word. */
154 last_bit = n_elms % SBITMAP_ELT_BITS;
155 if (last_bit)
157 bmap->elms[size - 1]
158 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
159 if (bmap->popcount)
160 bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]);
164 bmap->n_bits = n_elms;
165 bmap->size = size;
166 return bmap;
169 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
171 sbitmap
172 sbitmap_realloc (sbitmap src, unsigned int n_elms)
174 unsigned int bytes, size, amt;
175 sbitmap bmap;
177 size = SBITMAP_SET_SIZE (n_elms);
178 bytes = size * sizeof (SBITMAP_ELT_TYPE);
179 amt = (sizeof (struct simple_bitmap_def)
180 + bytes - sizeof (SBITMAP_ELT_TYPE));
182 if (SBITMAP_SIZE_BYTES (src) >= bytes)
184 src->n_bits = n_elms;
185 return src;
188 bmap = (sbitmap) xrealloc (src, amt);
189 bmap->n_bits = n_elms;
190 bmap->size = size;
191 return bmap;
194 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
196 sbitmap *
197 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms)
199 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes;
200 sbitmap *bitmap_vector;
202 size = SBITMAP_SET_SIZE (n_elms);
203 bytes = size * sizeof (SBITMAP_ELT_TYPE);
204 elm_bytes = (sizeof (struct simple_bitmap_def)
205 + bytes - sizeof (SBITMAP_ELT_TYPE));
206 vector_bytes = n_vecs * sizeof (sbitmap *);
208 /* Round up `vector_bytes' to account for the alignment requirements
209 of an sbitmap. One could allocate the vector-table and set of sbitmaps
210 separately, but that requires maintaining two pointers or creating
211 a cover struct to hold both pointers (so our result is still just
212 one pointer). Neither is a bad idea, but this is simpler for now. */
214 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
215 struct { char x; SBITMAP_ELT_TYPE y; } align;
216 int alignment = (char *) & align.y - & align.x;
217 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1);
220 amt = vector_bytes + (n_vecs * elm_bytes);
221 bitmap_vector = xmalloc (amt);
223 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes)
225 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset);
227 bitmap_vector[i] = b;
228 b->n_bits = n_elms;
229 b->size = size;
230 b->popcount = NULL;
233 return bitmap_vector;
236 /* Copy sbitmap SRC to DST. */
238 void
239 sbitmap_copy (sbitmap dst, const_sbitmap src)
241 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size);
242 if (dst->popcount)
243 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size);
246 /* Copy the first N elements of sbitmap SRC to DST. */
248 void
249 sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n)
251 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n);
252 if (dst->popcount)
253 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n);
256 /* Determine if a == b. */
258 sbitmap_equal (const_sbitmap a, const_sbitmap b)
260 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size);
263 /* Return true if the bitmap is empty. */
265 bool
266 sbitmap_empty_p (const_sbitmap bmap)
268 unsigned int i;
269 for (i=0; i<bmap->size; i++)
270 if (bmap->elms[i])
271 return false;
273 return true;
276 /* Zero all elements in a bitmap. */
278 void
279 sbitmap_zero (sbitmap bmap)
281 memset (bmap->elms, 0, SBITMAP_SIZE_BYTES (bmap));
282 if (bmap->popcount)
283 memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char));
286 /* Set all elements in a bitmap to ones. */
288 void
289 sbitmap_ones (sbitmap bmap)
291 unsigned int last_bit;
293 memset (bmap->elms, -1, SBITMAP_SIZE_BYTES (bmap));
294 if (bmap->popcount)
295 memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char));
297 last_bit = bmap->n_bits % SBITMAP_ELT_BITS;
298 if (last_bit)
300 bmap->elms[bmap->size - 1]
301 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit);
302 if (bmap->popcount)
303 bmap->popcount[bmap->size - 1]
304 = do_popcount (bmap->elms[bmap->size - 1]);
308 /* Zero a vector of N_VECS bitmaps. */
310 void
311 sbitmap_vector_zero (sbitmap *bmap, unsigned int n_vecs)
313 unsigned int i;
315 for (i = 0; i < n_vecs; i++)
316 sbitmap_zero (bmap[i]);
319 /* Set a vector of N_VECS bitmaps to ones. */
321 void
322 sbitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs)
324 unsigned int i;
326 for (i = 0; i < n_vecs; i++)
327 sbitmap_ones (bmap[i]);
330 /* Set DST to be A union (B - C).
331 DST = A | (B & ~C).
332 Returns true if any change is made. */
334 bool
335 sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
337 unsigned int i, n = dst->size;
338 sbitmap_ptr dstp = dst->elms;
339 const_sbitmap_ptr ap = a->elms;
340 const_sbitmap_ptr bp = b->elms;
341 const_sbitmap_ptr cp = c->elms;
342 SBITMAP_ELT_TYPE changed = 0;
344 gcc_assert (!dst->popcount);
346 for (i = 0; i < n; i++)
348 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
349 changed |= *dstp ^ tmp;
350 *dstp++ = tmp;
353 return changed != 0;
356 void
357 sbitmap_union_of_diff (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
359 unsigned int i, n = dst->size;
360 sbitmap_ptr dstp = dst->elms;
361 const_sbitmap_ptr ap = a->elms;
362 const_sbitmap_ptr bp = b->elms;
363 const_sbitmap_ptr cp = c->elms;
365 gcc_assert (!dst->popcount && !a->popcount
366 && !b->popcount && !c->popcount);
368 for (i = 0; i < n; i++)
369 *dstp++ = *ap++ | (*bp++ & ~*cp++);
372 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
374 void
375 sbitmap_not (sbitmap dst, const_sbitmap src)
377 unsigned int i, n = dst->size;
378 sbitmap_ptr dstp = dst->elms;
379 const_sbitmap_ptr srcp = src->elms;
380 unsigned int last_bit;
382 gcc_assert (!dst->popcount);
384 for (i = 0; i < n; i++)
385 *dstp++ = ~*srcp++;
387 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */
388 last_bit = src->n_bits % SBITMAP_ELT_BITS;
389 if (last_bit)
390 dst->elms[n-1] = dst->elms[n-1]
391 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit));
394 /* Set the bits in DST to be the difference between the bits
395 in A and the bits in B. i.e. dst = a & (~b). */
397 void
398 sbitmap_difference (sbitmap dst, const_sbitmap a, const_sbitmap b)
400 unsigned int i, dst_size = dst->size;
401 unsigned int min_size = dst->size;
402 sbitmap_ptr dstp = dst->elms;
403 const_sbitmap_ptr ap = a->elms;
404 const_sbitmap_ptr bp = b->elms;
406 gcc_assert (!dst->popcount);
408 /* A should be at least as large as DEST, to have a defined source. */
409 gcc_assert (a->size >= dst_size);
410 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
411 only copy the subtrahend into dest. */
412 if (b->size < min_size)
413 min_size = b->size;
414 for (i = 0; i < min_size; i++)
415 *dstp++ = *ap++ & (~*bp++);
416 /* Now fill the rest of dest from A, if B was too short.
417 This makes sense only when destination and A differ. */
418 if (dst != a && i != dst_size)
419 for (; i < dst_size; i++)
420 *dstp++ = *ap++;
423 /* Return true if there are any bits set in A are also set in B.
424 Return false otherwise. */
426 bool
427 sbitmap_any_common_bits (const_sbitmap a, const_sbitmap b)
429 const_sbitmap_ptr ap = a->elms;
430 const_sbitmap_ptr bp = b->elms;
431 unsigned int i, n;
433 n = MIN (a->size, b->size);
434 for (i = 0; i < n; i++)
435 if ((*ap++ & *bp++) != 0)
436 return true;
438 return false;
441 /* Set DST to be (A and B).
442 Return nonzero if any change is made. */
444 bool
445 sbitmap_a_and_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
447 unsigned int i, n = dst->size;
448 sbitmap_ptr dstp = dst->elms;
449 const_sbitmap_ptr ap = a->elms;
450 const_sbitmap_ptr bp = b->elms;
451 SBITMAP_ELT_TYPE changed = 0;
453 gcc_assert (!dst->popcount);
455 for (i = 0; i < n; i++)
457 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
458 changed |= *dstp ^ tmp;
459 *dstp++ = tmp;
462 return changed != 0;
465 void
466 sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
468 unsigned int i, n = dst->size;
469 sbitmap_ptr dstp = dst->elms;
470 const_sbitmap_ptr ap = a->elms;
471 const_sbitmap_ptr bp = b->elms;
472 bool has_popcount = dst->popcount != NULL;
473 unsigned char *popcountp = dst->popcount;
475 for (i = 0; i < n; i++)
477 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++;
478 if (has_popcount)
480 bool wordchanged = (*dstp ^ tmp) != 0;
481 if (wordchanged)
482 *popcountp = do_popcount (tmp);
483 popcountp++;
485 *dstp++ = tmp;
487 #ifdef BITMAP_DEBUGGING
488 if (has_popcount)
489 sbitmap_verify_popcount (dst);
490 #endif
493 /* Set DST to be (A xor B)).
494 Return nonzero if any change is made. */
496 bool
497 sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
499 unsigned int i, n = dst->size;
500 sbitmap_ptr dstp = dst->elms;
501 const_sbitmap_ptr ap = a->elms;
502 const_sbitmap_ptr bp = b->elms;
503 SBITMAP_ELT_TYPE changed = 0;
505 gcc_assert (!dst->popcount);
507 for (i = 0; i < n; i++)
509 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
510 changed |= *dstp ^ tmp;
511 *dstp++ = tmp;
514 return changed != 0;
517 void
518 sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
520 unsigned int i, n = dst->size;
521 sbitmap_ptr dstp = dst->elms;
522 const_sbitmap_ptr ap = a->elms;
523 const_sbitmap_ptr bp = b->elms;
524 bool has_popcount = dst->popcount != NULL;
525 unsigned char *popcountp = dst->popcount;
527 for (i = 0; i < n; i++)
529 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++;
530 if (has_popcount)
532 bool wordchanged = (*dstp ^ tmp) != 0;
533 if (wordchanged)
534 *popcountp = do_popcount (tmp);
535 popcountp++;
537 *dstp++ = tmp;
539 #ifdef BITMAP_DEBUGGING
540 if (has_popcount)
541 sbitmap_verify_popcount (dst);
542 #endif
545 /* Set DST to be (A or B)).
546 Return nonzero if any change is made. */
548 bool
549 sbitmap_a_or_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b)
551 unsigned int i, n = dst->size;
552 sbitmap_ptr dstp = dst->elms;
553 const_sbitmap_ptr ap = a->elms;
554 const_sbitmap_ptr bp = b->elms;
555 SBITMAP_ELT_TYPE changed = 0;
557 gcc_assert (!dst->popcount);
559 for (i = 0; i < n; i++)
561 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
562 changed |= *dstp ^ tmp;
563 *dstp++ = tmp;
566 return changed != 0;
569 void
570 sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b)
572 unsigned int i, n = dst->size;
573 sbitmap_ptr dstp = dst->elms;
574 const_sbitmap_ptr ap = a->elms;
575 const_sbitmap_ptr bp = b->elms;
576 bool has_popcount = dst->popcount != NULL;
577 unsigned char *popcountp = dst->popcount;
579 for (i = 0; i < n; i++)
581 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++;
582 if (has_popcount)
584 bool wordchanged = (*dstp ^ tmp) != 0;
585 if (wordchanged)
586 *popcountp = do_popcount (tmp);
587 popcountp++;
589 *dstp++ = tmp;
591 #ifdef BITMAP_DEBUGGING
592 if (has_popcount)
593 sbitmap_verify_popcount (dst);
594 #endif
597 /* Return nonzero if A is a subset of B. */
599 bool
600 sbitmap_a_subset_b_p (const_sbitmap a, const_sbitmap b)
602 unsigned int i, n = a->size;
603 const_sbitmap_ptr ap, bp;
605 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++)
606 if ((*ap | *bp) != *bp)
607 return false;
609 return true;
612 /* Set DST to be (A or (B and C)).
613 Return nonzero if any change is made. */
615 bool
616 sbitmap_a_or_b_and_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
618 unsigned int i, n = dst->size;
619 sbitmap_ptr dstp = dst->elms;
620 const_sbitmap_ptr ap = a->elms;
621 const_sbitmap_ptr bp = b->elms;
622 const_sbitmap_ptr cp = c->elms;
623 SBITMAP_ELT_TYPE changed = 0;
625 gcc_assert (!dst->popcount);
627 for (i = 0; i < n; i++)
629 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++);
630 changed |= *dstp ^ tmp;
631 *dstp++ = tmp;
634 return changed != 0;
637 void
638 sbitmap_a_or_b_and_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
640 unsigned int i, n = dst->size;
641 sbitmap_ptr dstp = dst->elms;
642 const_sbitmap_ptr ap = a->elms;
643 const_sbitmap_ptr bp = b->elms;
644 const_sbitmap_ptr cp = c->elms;
646 gcc_assert (!dst->popcount);
648 for (i = 0; i < n; i++)
649 *dstp++ = *ap++ | (*bp++ & *cp++);
652 /* Set DST to be (A and (B or C)).
653 Return nonzero if any change is made. */
655 bool
656 sbitmap_a_and_b_or_c_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
658 unsigned int i, n = dst->size;
659 sbitmap_ptr dstp = dst->elms;
660 const_sbitmap_ptr ap = a->elms;
661 const_sbitmap_ptr bp = b->elms;
662 const_sbitmap_ptr cp = c->elms;
663 SBITMAP_ELT_TYPE changed = 0;
665 gcc_assert (!dst->popcount);
667 for (i = 0; i < n; i++)
669 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++);
670 changed |= *dstp ^ tmp;
671 *dstp++ = tmp;
674 return changed != 0;
677 void
678 sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c)
680 unsigned int i, n = dst->size;
681 sbitmap_ptr dstp = dst->elms;
682 const_sbitmap_ptr ap = a->elms;
683 const_sbitmap_ptr bp = b->elms;
684 const_sbitmap_ptr cp = c->elms;
686 for (i = 0; i < n; i++)
687 *dstp++ = *ap++ & (*bp++ | *cp++);
690 #ifdef IN_GCC
691 /* Set the bitmap DST to the intersection of SRC of successors of
692 block number BB, using the new flow graph structures. */
694 void
695 sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb)
697 basic_block b = BASIC_BLOCK (bb);
698 unsigned int set_size = dst->size;
699 edge e;
700 unsigned ix;
702 gcc_assert (!dst->popcount);
704 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++)
706 e = EDGE_SUCC (b, ix);
707 if (e->dest == EXIT_BLOCK_PTR)
708 continue;
710 sbitmap_copy (dst, src[e->dest->index]);
711 break;
714 if (e == 0)
715 sbitmap_ones (dst);
716 else
717 for (++ix; ix < EDGE_COUNT (b->succs); ix++)
719 unsigned int i;
720 sbitmap_ptr p, r;
722 e = EDGE_SUCC (b, ix);
723 if (e->dest == EXIT_BLOCK_PTR)
724 continue;
726 p = src[e->dest->index]->elms;
727 r = dst->elms;
728 for (i = 0; i < set_size; i++)
729 *r++ &= *p++;
733 /* Set the bitmap DST to the intersection of SRC of predecessors of
734 block number BB, using the new flow graph structures. */
736 void
737 sbitmap_intersection_of_preds (sbitmap dst, sbitmap *src, int bb)
739 basic_block b = BASIC_BLOCK (bb);
740 unsigned int set_size = dst->size;
741 edge e;
742 unsigned ix;
744 gcc_assert (!dst->popcount);
746 for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++)
748 e = EDGE_PRED (b, ix);
749 if (e->src == ENTRY_BLOCK_PTR)
750 continue;
752 sbitmap_copy (dst, src[e->src->index]);
753 break;
756 if (e == 0)
757 sbitmap_ones (dst);
758 else
759 for (++ix; ix < EDGE_COUNT (b->preds); ix++)
761 unsigned int i;
762 sbitmap_ptr p, r;
764 e = EDGE_PRED (b, ix);
765 if (e->src == ENTRY_BLOCK_PTR)
766 continue;
768 p = src[e->src->index]->elms;
769 r = dst->elms;
770 for (i = 0; i < set_size; i++)
771 *r++ &= *p++;
775 /* Set the bitmap DST to the union of SRC of successors of
776 block number BB, using the new flow graph structures. */
778 void
779 sbitmap_union_of_succs (sbitmap dst, sbitmap *src, int bb)
781 basic_block b = BASIC_BLOCK (bb);
782 unsigned int set_size = dst->size;
783 edge e;
784 unsigned ix;
786 gcc_assert (!dst->popcount);
788 for (ix = 0; ix < EDGE_COUNT (b->succs); ix++)
790 e = EDGE_SUCC (b, ix);
791 if (e->dest == EXIT_BLOCK_PTR)
792 continue;
794 sbitmap_copy (dst, src[e->dest->index]);
795 break;
798 if (ix == EDGE_COUNT (b->succs))
799 sbitmap_zero (dst);
800 else
801 for (ix++; ix < EDGE_COUNT (b->succs); ix++)
803 unsigned int i;
804 sbitmap_ptr p, r;
806 e = EDGE_SUCC (b, ix);
807 if (e->dest == EXIT_BLOCK_PTR)
808 continue;
810 p = src[e->dest->index]->elms;
811 r = dst->elms;
812 for (i = 0; i < set_size; i++)
813 *r++ |= *p++;
817 /* Set the bitmap DST to the union of SRC of predecessors of
818 block number BB, using the new flow graph structures. */
820 void
821 sbitmap_union_of_preds (sbitmap dst, sbitmap *src, int bb)
823 basic_block b = BASIC_BLOCK (bb);
824 unsigned int set_size = dst->size;
825 edge e;
826 unsigned ix;
828 gcc_assert (!dst->popcount);
830 for (ix = 0; ix < EDGE_COUNT (b->preds); ix++)
832 e = EDGE_PRED (b, ix);
833 if (e->src== ENTRY_BLOCK_PTR)
834 continue;
836 sbitmap_copy (dst, src[e->src->index]);
837 break;
840 if (ix == EDGE_COUNT (b->preds))
841 sbitmap_zero (dst);
842 else
843 for (ix++; ix < EDGE_COUNT (b->preds); ix++)
845 unsigned int i;
846 sbitmap_ptr p, r;
848 e = EDGE_PRED (b, ix);
849 if (e->src == ENTRY_BLOCK_PTR)
850 continue;
852 p = src[e->src->index]->elms;
853 r = dst->elms;
854 for (i = 0; i < set_size; i++)
855 *r++ |= *p++;
858 #endif
860 /* Return number of first bit set in the bitmap, -1 if none. */
863 sbitmap_first_set_bit (const_sbitmap bmap)
865 unsigned int n = 0;
866 sbitmap_iterator sbi;
868 EXECUTE_IF_SET_IN_SBITMAP (bmap, 0, n, sbi)
869 return n;
870 return -1;
873 /* Return number of last bit set in the bitmap, -1 if none. */
876 sbitmap_last_set_bit (const_sbitmap bmap)
878 int i;
879 const SBITMAP_ELT_TYPE *const ptr = bmap->elms;
881 for (i = bmap->size - 1; i >= 0; i--)
883 const SBITMAP_ELT_TYPE word = ptr[i];
885 if (word != 0)
887 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1;
888 SBITMAP_ELT_TYPE mask
889 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1);
891 while (1)
893 if ((word & mask) != 0)
894 return index;
896 mask >>= 1;
897 index--;
902 return -1;
905 void
906 dump_sbitmap (FILE *file, const_sbitmap bmap)
908 unsigned int i, n, j;
909 unsigned int set_size = bmap->size;
910 unsigned int total_bits = bmap->n_bits;
912 fprintf (file, " ");
913 for (i = n = 0; i < set_size && n < total_bits; i++)
914 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++)
916 if (n != 0 && n % 10 == 0)
917 fprintf (file, " ");
919 fprintf (file, "%d",
920 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0);
923 fprintf (file, "\n");
926 void
927 dump_sbitmap_file (FILE *file, const_sbitmap bmap)
929 unsigned int i, pos;
931 fprintf (file, "n_bits = %d, set = {", bmap->n_bits);
933 for (pos = 30, i = 0; i < bmap->n_bits; i++)
934 if (TEST_BIT (bmap, i))
936 if (pos > 70)
938 fprintf (file, "\n ");
939 pos = 0;
942 fprintf (file, "%d ", i);
943 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000);
946 fprintf (file, "}\n");
949 void
950 debug_sbitmap (const_sbitmap bmap)
952 dump_sbitmap_file (stderr, bmap);
955 void
956 dump_sbitmap_vector (FILE *file, const char *title, const char *subtitle,
957 sbitmap *bmaps, int n_maps)
959 int bb;
961 fprintf (file, "%s\n", title);
962 for (bb = 0; bb < n_maps; bb++)
964 fprintf (file, "%s %d\n", subtitle, bb);
965 dump_sbitmap (file, bmaps[bb]);
968 fprintf (file, "\n");
971 #if GCC_VERSION < 3400
972 /* Table of number of set bits in a character, indexed by value of char. */
973 static const unsigned char popcount_table[] =
975 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
976 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
977 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
978 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
979 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
980 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
981 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
982 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
985 /* Count the bits in an SBITMAP element A. */
987 static unsigned long
988 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a)
990 unsigned long ret = 0;
991 unsigned i;
993 if (a == 0)
994 return 0;
996 /* Just do this the table way for now */
997 for (i = 0; i < SBITMAP_ELT_BITS; i += 8)
998 ret += popcount_table[(a >> i) & 0xff];
999 return ret;
1001 #endif
1003 /* Count the number of bits in SBITMAP a, up to bit MAXBIT. */
1005 unsigned long
1006 sbitmap_popcount (const_sbitmap a, unsigned long maxbit)
1008 unsigned long count = 0;
1009 unsigned ix;
1010 unsigned int lastword;
1012 if (maxbit == 0)
1013 return 0;
1015 if (maxbit >= a->n_bits)
1016 maxbit = a->n_bits;
1018 /* Count the bits in the full word. */
1019 lastword = MIN (a->size, SBITMAP_SET_SIZE (maxbit + 1) - 1);
1020 for (ix = 0; ix < lastword; ix++)
1022 if (a->popcount)
1024 count += a->popcount[ix];
1025 #ifdef BITMAP_DEBUGGING
1026 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix]));
1027 #endif
1029 else
1030 count += do_popcount (a->elms[ix]);
1033 /* Count the remaining bits. */
1034 if (lastword < a->size)
1036 unsigned int bitindex;
1037 SBITMAP_ELT_TYPE theword = a->elms[lastword];
1039 bitindex = maxbit % SBITMAP_ELT_BITS;
1040 if (bitindex != 0)
1042 theword &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - bitindex);
1043 count += do_popcount (theword);
1046 return count;