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 2, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
28 #include "hard-reg-set.h"
30 #include "basic-block.h"
32 #if GCC_VERSION >= 3400
33 #if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
34 #define do_popcount(x) __builtin_popcountl(x)
35 #elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
36 #define do_popcount(x) __builtin_popcountll(x)
38 #error "internal error: sbitmap.h and hwint.h are inconsistent"
41 static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE
);
42 #define do_popcount(x) sbitmap_elt_popcount((x))
45 /* This macro controls debugging that is as expensive as the
46 operations it verifies. */
48 /* #define BITMAP_DEBUGGING */
49 #ifdef BITMAP_DEBUGGING
51 /* Verify the population count of sbitmap A matches the cached value,
52 if there is a cached value. */
55 sbitmap_verify_popcount (sbitmap a
)
58 unsigned int lastword
;
64 for (ix
= 0; ix
< lastword
; ix
++)
65 gcc_assert (a
->popcount
[ix
] == do_popcount (a
->elms
[ix
]));
69 /* Bitmap manipulation routines. */
71 /* Allocate a simple bitmap of N_ELMS bits. */
74 sbitmap_alloc (unsigned int n_elms
)
76 unsigned int bytes
, size
, amt
;
79 size
= SBITMAP_SET_SIZE (n_elms
);
80 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
81 amt
= (sizeof (struct simple_bitmap_def
)
82 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
84 bmap
->n_bits
= n_elms
;
86 bmap
->popcount
= NULL
;
90 /* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */
93 sbitmap_alloc_with_popcount (unsigned int n_elms
)
97 bmap
= sbitmap_alloc (n_elms
);
98 bmap
->popcount
= xmalloc (bmap
->size
* sizeof (unsigned char));
102 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the
103 size of BMAP, clear the new bits to zero if the DEF argument
104 is zero, and set them to one otherwise. */
107 sbitmap_resize (sbitmap bmap
, unsigned int n_elms
, int def
)
109 unsigned int bytes
, size
, amt
;
110 unsigned int last_bit
;
112 size
= SBITMAP_SET_SIZE (n_elms
);
113 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
114 if (bytes
> SBITMAP_SIZE_BYTES (bmap
))
116 amt
= (sizeof (struct simple_bitmap_def
)
117 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
118 bmap
= xrealloc (bmap
, amt
);
120 bmap
->popcount
= xrealloc (bmap
->popcount
,
121 size
* sizeof (unsigned char));
124 if (n_elms
> bmap
->n_bits
)
128 memset (bmap
->elms
+ bmap
->size
, -1,
129 bytes
- SBITMAP_SIZE_BYTES (bmap
));
131 /* Set the new bits if the original last element. */
132 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
134 bmap
->elms
[bmap
->size
- 1]
135 |= ~((SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
));
137 /* Clear the unused bit in the new last element. */
138 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
141 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
145 memset (bmap
->elms
+ bmap
->size
, 0,
146 bytes
- SBITMAP_SIZE_BYTES (bmap
));
148 memset (bmap
->popcount
+ bmap
->size
, 0,
149 (size
* sizeof (unsigned char))
150 - (bmap
->size
* sizeof (unsigned char)));
154 else if (n_elms
< bmap
->n_bits
)
156 /* Clear the surplus bits in the last word. */
157 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
161 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
163 bmap
->popcount
[size
- 1] = do_popcount (bmap
->elms
[size
- 1]);
167 bmap
->n_bits
= n_elms
;
172 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */
175 sbitmap_realloc (sbitmap src
, unsigned int n_elms
)
177 unsigned int bytes
, size
, amt
;
180 size
= SBITMAP_SET_SIZE (n_elms
);
181 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
182 amt
= (sizeof (struct simple_bitmap_def
)
183 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
185 if (SBITMAP_SIZE_BYTES (src
) >= bytes
)
187 src
->n_bits
= n_elms
;
191 bmap
= (sbitmap
) xrealloc (src
, amt
);
192 bmap
->n_bits
= n_elms
;
197 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
200 sbitmap_vector_alloc (unsigned int n_vecs
, unsigned int n_elms
)
202 unsigned int i
, bytes
, offset
, elm_bytes
, size
, amt
, vector_bytes
;
203 sbitmap
*bitmap_vector
;
205 size
= SBITMAP_SET_SIZE (n_elms
);
206 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
207 elm_bytes
= (sizeof (struct simple_bitmap_def
)
208 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
209 vector_bytes
= n_vecs
* sizeof (sbitmap
*);
211 /* Round up `vector_bytes' to account for the alignment requirements
212 of an sbitmap. One could allocate the vector-table and set of sbitmaps
213 separately, but that requires maintaining two pointers or creating
214 a cover struct to hold both pointers (so our result is still just
215 one pointer). Neither is a bad idea, but this is simpler for now. */
217 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
218 struct { char x
; SBITMAP_ELT_TYPE y
; } align
;
219 int alignment
= (char *) & align
.y
- & align
.x
;
220 vector_bytes
= (vector_bytes
+ alignment
- 1) & ~ (alignment
- 1);
223 amt
= vector_bytes
+ (n_vecs
* elm_bytes
);
224 bitmap_vector
= xmalloc (amt
);
226 for (i
= 0, offset
= vector_bytes
; i
< n_vecs
; i
++, offset
+= elm_bytes
)
228 sbitmap b
= (sbitmap
) ((char *) bitmap_vector
+ offset
);
230 bitmap_vector
[i
] = b
;
236 return bitmap_vector
;
239 /* Copy sbitmap SRC to DST. */
242 sbitmap_copy (sbitmap dst
, sbitmap src
)
244 memcpy (dst
->elms
, src
->elms
, sizeof (SBITMAP_ELT_TYPE
) * dst
->size
);
246 memcpy (dst
->popcount
, src
->popcount
, sizeof (unsigned char) * dst
->size
);
249 /* Copy the first N elements of sbitmap SRC to DST. */
252 sbitmap_copy_n (sbitmap dst
, sbitmap src
, unsigned int n
)
254 memcpy (dst
->elms
, src
->elms
, sizeof (SBITMAP_ELT_TYPE
) * n
);
256 memcpy (dst
->popcount
, src
->popcount
, sizeof (unsigned char) * n
);
259 /* Determine if a == b. */
261 sbitmap_equal (sbitmap a
, sbitmap b
)
263 return !memcmp (a
->elms
, b
->elms
, sizeof (SBITMAP_ELT_TYPE
) * a
->size
);
266 /* Return true if the bitmap is empty. */
269 sbitmap_empty_p (sbitmap bmap
)
272 for (i
=0; i
<bmap
->size
; i
++)
279 /* Zero all elements in a bitmap. */
282 sbitmap_zero (sbitmap bmap
)
284 memset (bmap
->elms
, 0, SBITMAP_SIZE_BYTES (bmap
));
286 memset (bmap
->popcount
, 0, bmap
->size
* sizeof (unsigned char));
289 /* Set all elements in a bitmap to ones. */
292 sbitmap_ones (sbitmap bmap
)
294 unsigned int last_bit
;
296 memset (bmap
->elms
, -1, SBITMAP_SIZE_BYTES (bmap
));
298 memset (bmap
->popcount
, -1, bmap
->size
* sizeof (unsigned char));
300 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
303 bmap
->elms
[bmap
->size
- 1]
304 = (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
306 bmap
->popcount
[bmap
->size
- 1]
307 = do_popcount (bmap
->elms
[bmap
->size
- 1]);
311 /* Zero a vector of N_VECS bitmaps. */
314 sbitmap_vector_zero (sbitmap
*bmap
, unsigned int n_vecs
)
318 for (i
= 0; i
< n_vecs
; i
++)
319 sbitmap_zero (bmap
[i
]);
322 /* Set a vector of N_VECS bitmaps to ones. */
325 sbitmap_vector_ones (sbitmap
*bmap
, unsigned int n_vecs
)
329 for (i
= 0; i
< n_vecs
; i
++)
330 sbitmap_ones (bmap
[i
]);
333 /* Set DST to be A union (B - C).
335 Returns true if any change is made. */
338 sbitmap_union_of_diff_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
340 unsigned int i
, n
= dst
->size
;
341 sbitmap_ptr dstp
= dst
->elms
;
342 sbitmap_ptr ap
= a
->elms
;
343 sbitmap_ptr bp
= b
->elms
;
344 sbitmap_ptr cp
= c
->elms
;
345 SBITMAP_ELT_TYPE changed
= 0;
347 gcc_assert (!dst
->popcount
);
349 for (i
= 0; i
< n
; i
++)
351 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & ~*cp
++);
352 changed
|= *dstp
^ tmp
;
360 sbitmap_union_of_diff (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
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 sbitmap_ptr cp
= c
->elms
;
368 gcc_assert (!dst
->popcount
&& !a
->popcount
369 && !b
->popcount
&& !c
->popcount
);
371 for (i
= 0; i
< n
; i
++)
372 *dstp
++ = *ap
++ | (*bp
++ & ~*cp
++);
375 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
378 sbitmap_not (sbitmap dst
, sbitmap src
)
380 unsigned int i
, n
= dst
->size
;
381 sbitmap_ptr dstp
= dst
->elms
;
382 sbitmap_ptr srcp
= src
->elms
;
383 unsigned int last_bit
;
385 gcc_assert (!dst
->popcount
);
387 for (i
= 0; i
< n
; i
++)
390 /* Zero all bits past n_bits, by ANDing dst with sbitmap_ones. */
391 last_bit
= src
->n_bits
% SBITMAP_ELT_BITS
;
393 dst
->elms
[n
-1] = dst
->elms
[n
-1]
394 & ((SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
));
397 /* Set the bits in DST to be the difference between the bits
398 in A and the bits in B. i.e. dst = a & (~b). */
401 sbitmap_difference (sbitmap dst
, sbitmap a
, sbitmap b
)
403 unsigned int i
, dst_size
= dst
->size
;
404 unsigned int min_size
= dst
->size
;
405 sbitmap_ptr dstp
= dst
->elms
;
406 sbitmap_ptr ap
= a
->elms
;
407 sbitmap_ptr bp
= b
->elms
;
409 gcc_assert (!dst
->popcount
);
411 /* A should be at least as large as DEST, to have a defined source. */
412 gcc_assert (a
->size
>= dst_size
);
413 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
414 only copy the subtrahend into dest. */
415 if (b
->size
< min_size
)
417 for (i
= 0; i
< min_size
; i
++)
418 *dstp
++ = *ap
++ & (~*bp
++);
419 /* Now fill the rest of dest from A, if B was too short.
420 This makes sense only when destination and A differ. */
421 if (dst
!= a
&& i
!= dst_size
)
422 for (; i
< dst_size
; i
++)
426 /* Return true if there are any bits set in A are also set in B.
427 Return false otherwise. */
430 sbitmap_any_common_bits (sbitmap a
, sbitmap b
)
432 sbitmap_ptr ap
= a
->elms
;
433 sbitmap_ptr bp
= b
->elms
;
436 n
= MIN (a
->size
, b
->size
);
437 for (i
= 0; i
< n
; i
++)
438 if ((*ap
++ & *bp
++) != 0)
444 /* Set DST to be (A and B).
445 Return nonzero if any change is made. */
448 sbitmap_a_and_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
450 unsigned int i
, n
= dst
->size
;
451 sbitmap_ptr dstp
= dst
->elms
;
452 sbitmap_ptr ap
= a
->elms
;
453 sbitmap_ptr bp
= b
->elms
;
454 SBITMAP_ELT_TYPE changed
= 0;
456 gcc_assert (!dst
->popcount
);
458 for (i
= 0; i
< n
; i
++)
460 SBITMAP_ELT_TYPE tmp
= *ap
++ & *bp
++;
461 changed
|= *dstp
^ tmp
;
469 sbitmap_a_and_b (sbitmap dst
, sbitmap a
, sbitmap b
)
471 unsigned int i
, n
= dst
->size
;
472 sbitmap_ptr dstp
= dst
->elms
;
473 sbitmap_ptr ap
= a
->elms
;
474 sbitmap_ptr bp
= b
->elms
;
475 bool has_popcount
= dst
->popcount
!= NULL
;
476 unsigned char *popcountp
= dst
->popcount
;
478 for (i
= 0; i
< n
; i
++)
480 SBITMAP_ELT_TYPE tmp
= *ap
++ & *bp
++;
483 bool wordchanged
= (*dstp
^ tmp
) != 0;
485 *popcountp
= do_popcount (tmp
);
490 #ifdef BITMAP_DEBUGGING
492 sbitmap_verify_popcount (dst
);
496 /* Set DST to be (A xor B)).
497 Return nonzero if any change is made. */
500 sbitmap_a_xor_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
502 unsigned int i
, n
= dst
->size
;
503 sbitmap_ptr dstp
= dst
->elms
;
504 sbitmap_ptr ap
= a
->elms
;
505 sbitmap_ptr bp
= b
->elms
;
506 SBITMAP_ELT_TYPE changed
= 0;
508 gcc_assert (!dst
->popcount
);
510 for (i
= 0; i
< n
; i
++)
512 SBITMAP_ELT_TYPE tmp
= *ap
++ ^ *bp
++;
513 changed
|= *dstp
^ tmp
;
521 sbitmap_a_xor_b (sbitmap dst
, sbitmap a
, sbitmap b
)
523 unsigned int i
, n
= dst
->size
;
524 sbitmap_ptr dstp
= dst
->elms
;
525 sbitmap_ptr ap
= a
->elms
;
526 sbitmap_ptr bp
= b
->elms
;
527 bool has_popcount
= dst
->popcount
!= NULL
;
528 unsigned char *popcountp
= dst
->popcount
;
530 for (i
= 0; i
< n
; i
++)
532 SBITMAP_ELT_TYPE tmp
= *ap
++ ^ *bp
++;
535 bool wordchanged
= (*dstp
^ tmp
) != 0;
537 *popcountp
= do_popcount (tmp
);
542 #ifdef BITMAP_DEBUGGING
544 sbitmap_verify_popcount (dst
);
548 /* Set DST to be (A or B)).
549 Return nonzero if any change is made. */
552 sbitmap_a_or_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
554 unsigned int i
, n
= dst
->size
;
555 sbitmap_ptr dstp
= dst
->elms
;
556 sbitmap_ptr ap
= a
->elms
;
557 sbitmap_ptr bp
= b
->elms
;
558 SBITMAP_ELT_TYPE changed
= 0;
560 gcc_assert (!dst
->popcount
);
562 for (i
= 0; i
< n
; i
++)
564 SBITMAP_ELT_TYPE tmp
= *ap
++ | *bp
++;
565 changed
|= *dstp
^ tmp
;
573 sbitmap_a_or_b (sbitmap dst
, sbitmap a
, sbitmap b
)
575 unsigned int i
, n
= dst
->size
;
576 sbitmap_ptr dstp
= dst
->elms
;
577 sbitmap_ptr ap
= a
->elms
;
578 sbitmap_ptr bp
= b
->elms
;
579 bool has_popcount
= dst
->popcount
!= NULL
;
580 unsigned char *popcountp
= dst
->popcount
;
582 for (i
= 0; i
< n
; i
++)
584 SBITMAP_ELT_TYPE tmp
= *ap
++ | *bp
++;
587 bool wordchanged
= (*dstp
^ tmp
) != 0;
589 *popcountp
= do_popcount (tmp
);
594 #ifdef BITMAP_DEBUGGING
596 sbitmap_verify_popcount (dst
);
600 /* Return nonzero if A is a subset of B. */
603 sbitmap_a_subset_b_p (sbitmap a
, sbitmap b
)
605 unsigned int i
, n
= a
->size
;
608 for (ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< n
; i
++, ap
++, bp
++)
609 if ((*ap
| *bp
) != *bp
)
615 /* Set DST to be (A or (B and C)).
616 Return nonzero if any change is made. */
619 sbitmap_a_or_b_and_c_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
621 unsigned int i
, n
= dst
->size
;
622 sbitmap_ptr dstp
= dst
->elms
;
623 sbitmap_ptr ap
= a
->elms
;
624 sbitmap_ptr bp
= b
->elms
;
625 sbitmap_ptr cp
= c
->elms
;
626 SBITMAP_ELT_TYPE changed
= 0;
628 gcc_assert (!dst
->popcount
);
630 for (i
= 0; i
< n
; i
++)
632 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & *cp
++);
633 changed
|= *dstp
^ tmp
;
641 sbitmap_a_or_b_and_c (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
643 unsigned int i
, n
= dst
->size
;
644 sbitmap_ptr dstp
= dst
->elms
;
645 sbitmap_ptr ap
= a
->elms
;
646 sbitmap_ptr bp
= b
->elms
;
647 sbitmap_ptr cp
= c
->elms
;
649 gcc_assert (!dst
->popcount
);
651 for (i
= 0; i
< n
; i
++)
652 *dstp
++ = *ap
++ | (*bp
++ & *cp
++);
655 /* Set DST to be (A and (B or C)).
656 Return nonzero if any change is made. */
659 sbitmap_a_and_b_or_c_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
661 unsigned int i
, n
= dst
->size
;
662 sbitmap_ptr dstp
= dst
->elms
;
663 sbitmap_ptr ap
= a
->elms
;
664 sbitmap_ptr bp
= b
->elms
;
665 sbitmap_ptr cp
= c
->elms
;
666 SBITMAP_ELT_TYPE changed
= 0;
668 gcc_assert (!dst
->popcount
);
670 for (i
= 0; i
< n
; i
++)
672 SBITMAP_ELT_TYPE tmp
= *ap
++ & (*bp
++ | *cp
++);
673 changed
|= *dstp
^ tmp
;
681 sbitmap_a_and_b_or_c (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
683 unsigned int i
, n
= dst
->size
;
684 sbitmap_ptr dstp
= dst
->elms
;
685 sbitmap_ptr ap
= a
->elms
;
686 sbitmap_ptr bp
= b
->elms
;
687 sbitmap_ptr cp
= c
->elms
;
689 for (i
= 0; i
< n
; i
++)
690 *dstp
++ = *ap
++ & (*bp
++ | *cp
++);
694 /* Set the bitmap DST to the intersection of SRC of successors of
695 block number BB, using the new flow graph structures. */
698 sbitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, int bb
)
700 basic_block b
= BASIC_BLOCK (bb
);
701 unsigned int set_size
= dst
->size
;
705 gcc_assert (!dst
->popcount
);
707 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
709 e
= EDGE_SUCC (b
, ix
);
710 if (e
->dest
== EXIT_BLOCK_PTR
)
713 sbitmap_copy (dst
, src
[e
->dest
->index
]);
720 for (++ix
; ix
< EDGE_COUNT (b
->succs
); ix
++)
725 e
= EDGE_SUCC (b
, ix
);
726 if (e
->dest
== EXIT_BLOCK_PTR
)
729 p
= src
[e
->dest
->index
]->elms
;
731 for (i
= 0; i
< set_size
; i
++)
736 /* Set the bitmap DST to the intersection of SRC of predecessors of
737 block number BB, using the new flow graph structures. */
740 sbitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, int bb
)
742 basic_block b
= BASIC_BLOCK (bb
);
743 unsigned int set_size
= dst
->size
;
747 gcc_assert (!dst
->popcount
);
749 for (e
= NULL
, ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
751 e
= EDGE_PRED (b
, ix
);
752 if (e
->src
== ENTRY_BLOCK_PTR
)
755 sbitmap_copy (dst
, src
[e
->src
->index
]);
762 for (++ix
; ix
< EDGE_COUNT (b
->preds
); ix
++)
767 e
= EDGE_PRED (b
, ix
);
768 if (e
->src
== ENTRY_BLOCK_PTR
)
771 p
= src
[e
->src
->index
]->elms
;
773 for (i
= 0; i
< set_size
; i
++)
778 /* Set the bitmap DST to the union of SRC of successors of
779 block number BB, using the new flow graph structures. */
782 sbitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, int bb
)
784 basic_block b
= BASIC_BLOCK (bb
);
785 unsigned int set_size
= dst
->size
;
789 gcc_assert (!dst
->popcount
);
791 for (ix
= 0; ix
< EDGE_COUNT (b
->succs
); ix
++)
793 e
= EDGE_SUCC (b
, ix
);
794 if (e
->dest
== EXIT_BLOCK_PTR
)
797 sbitmap_copy (dst
, src
[e
->dest
->index
]);
801 if (ix
== EDGE_COUNT (b
->succs
))
804 for (ix
++; ix
< EDGE_COUNT (b
->succs
); ix
++)
809 e
= EDGE_SUCC (b
, ix
);
810 if (e
->dest
== EXIT_BLOCK_PTR
)
813 p
= src
[e
->dest
->index
]->elms
;
815 for (i
= 0; i
< set_size
; i
++)
820 /* Set the bitmap DST to the union of SRC of predecessors of
821 block number BB, using the new flow graph structures. */
824 sbitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, int bb
)
826 basic_block b
= BASIC_BLOCK (bb
);
827 unsigned int set_size
= dst
->size
;
831 gcc_assert (!dst
->popcount
);
833 for (ix
= 0; ix
< EDGE_COUNT (b
->preds
); ix
++)
835 e
= EDGE_PRED (b
, ix
);
836 if (e
->src
== ENTRY_BLOCK_PTR
)
839 sbitmap_copy (dst
, src
[e
->src
->index
]);
843 if (ix
== EDGE_COUNT (b
->preds
))
846 for (ix
++; ix
< EDGE_COUNT (b
->preds
); ix
++)
851 e
= EDGE_PRED (b
, ix
);
852 if (e
->src
== ENTRY_BLOCK_PTR
)
855 p
= src
[e
->src
->index
]->elms
;
857 for (i
= 0; i
< set_size
; i
++)
863 /* Return number of first bit set in the bitmap, -1 if none. */
866 sbitmap_first_set_bit (sbitmap bmap
)
869 sbitmap_iterator sbi
;
871 EXECUTE_IF_SET_IN_SBITMAP (bmap
, 0, n
, sbi
)
876 /* Return number of last bit set in the bitmap, -1 if none. */
879 sbitmap_last_set_bit (sbitmap bmap
)
882 SBITMAP_ELT_TYPE
*ptr
= bmap
->elms
;
884 for (i
= bmap
->size
- 1; i
>= 0; i
--)
886 SBITMAP_ELT_TYPE word
= ptr
[i
];
890 unsigned int index
= (i
+ 1) * SBITMAP_ELT_BITS
- 1;
891 SBITMAP_ELT_TYPE mask
892 = (SBITMAP_ELT_TYPE
) 1 << (SBITMAP_ELT_BITS
- 1);
896 if ((word
& mask
) != 0)
909 dump_sbitmap (FILE *file
, sbitmap bmap
)
911 unsigned int i
, n
, j
;
912 unsigned int set_size
= bmap
->size
;
913 unsigned int total_bits
= bmap
->n_bits
;
916 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
917 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
919 if (n
!= 0 && n
% 10 == 0)
923 (bmap
->elms
[i
] & ((SBITMAP_ELT_TYPE
) 1 << j
)) != 0);
926 fprintf (file
, "\n");
930 dump_sbitmap_file (FILE *file
, sbitmap bmap
)
934 fprintf (file
, "n_bits = %d, set = {", bmap
->n_bits
);
936 for (pos
= 30, i
= 0; i
< bmap
->n_bits
; i
++)
937 if (TEST_BIT (bmap
, i
))
941 fprintf (file
, "\n ");
945 fprintf (file
, "%d ", i
);
946 pos
+= 2 + (i
>= 10) + (i
>= 100) + (i
>= 1000);
949 fprintf (file
, "}\n");
953 debug_sbitmap (sbitmap bmap
)
955 dump_sbitmap_file (stderr
, bmap
);
959 dump_sbitmap_vector (FILE *file
, const char *title
, const char *subtitle
,
960 sbitmap
*bmaps
, int n_maps
)
964 fprintf (file
, "%s\n", title
);
965 for (bb
= 0; bb
< n_maps
; bb
++)
967 fprintf (file
, "%s %d\n", subtitle
, bb
);
968 dump_sbitmap (file
, bmaps
[bb
]);
971 fprintf (file
, "\n");
974 #if GCC_VERSION < 3400
975 /* Table of number of set bits in a character, indexed by value of char. */
976 static unsigned char popcount_table
[] =
978 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,
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 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,
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 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,
983 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,
984 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,
985 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,
988 /* Count the bits in an SBITMAP element A. */
991 sbitmap_elt_popcount (SBITMAP_ELT_TYPE a
)
993 unsigned long ret
= 0;
999 /* Just do this the table way for now */
1000 for (i
= 0; i
< SBITMAP_ELT_BITS
; i
+= 8)
1001 ret
+= popcount_table
[(a
>> i
) & 0xff];
1006 /* Count the number of bits in SBITMAP a, up to bit MAXBIT. */
1009 sbitmap_popcount (sbitmap a
, unsigned long maxbit
)
1011 unsigned long count
= 0;
1013 unsigned int lastword
;
1018 if (maxbit
>= a
->n_bits
)
1021 /* Count the bits in the full word. */
1022 lastword
= MIN (a
->size
, SBITMAP_SET_SIZE (maxbit
+ 1) - 1);
1023 for (ix
= 0; ix
< lastword
; ix
++)
1027 count
+= a
->popcount
[ix
];
1028 #ifdef BITMAP_DEBUGGING
1029 gcc_assert (a
->popcount
[ix
] == do_popcount (a
->elms
[ix
]));
1033 count
+= do_popcount (a
->elms
[ix
]);
1036 /* Count the remaining bits. */
1037 if (lastword
< a
->size
)
1039 unsigned int bitindex
;
1040 SBITMAP_ELT_TYPE theword
= a
->elms
[lastword
];
1042 bitindex
= maxbit
% SBITMAP_ELT_BITS
;
1045 theword
&= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- bitindex
);
1046 count
+= do_popcount (theword
);