2 Copyright (C) 1999, 2000, 2002, 2003 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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 /* Bitmap manipulation routines. */
32 /* Allocate a simple bitmap of N_ELMS bits. */
35 sbitmap_alloc (n_elms
)
38 unsigned int bytes
, size
, amt
;
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
= (sbitmap
) xmalloc (amt
);
46 bmap
->n_bits
= n_elms
;
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. */
57 sbitmap_resize (bmap
, n_elms
, def
)
62 unsigned int bytes
, size
, amt
;
63 unsigned int last_bit
;
65 size
= SBITMAP_SET_SIZE (n_elms
);
66 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
67 if (bytes
> bmap
->bytes
)
69 amt
= (sizeof (struct simple_bitmap_def
)
70 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
71 bmap
= (sbitmap
) xrealloc ((PTR
) bmap
, amt
);
74 if (n_elms
> bmap
->n_bits
)
78 memset ((PTR
) (bmap
->elms
+ bmap
->size
), -1, bytes
- bmap
->bytes
);
80 /* Set the new bits if the original last element. */
81 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
83 bmap
->elms
[bmap
->size
- 1]
84 |= ~((SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
));
86 /* Clear the unused bit in the new last element. */
87 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
90 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
93 memset ((PTR
) (bmap
->elms
+ bmap
->size
), 0, bytes
- bmap
->bytes
);
95 else if (n_elms
< bmap
->n_bits
)
97 /* Clear the surplus bits in the last word. */
98 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
101 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
104 bmap
->n_bits
= n_elms
;
110 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
113 sbitmap_vector_alloc (n_vecs
, n_elms
)
114 unsigned int n_vecs
, n_elms
;
116 unsigned int i
, bytes
, offset
, elm_bytes
, size
, amt
, vector_bytes
;
117 sbitmap
*bitmap_vector
;
119 size
= SBITMAP_SET_SIZE (n_elms
);
120 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
121 elm_bytes
= (sizeof (struct simple_bitmap_def
)
122 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
123 vector_bytes
= n_vecs
* sizeof (sbitmap
*);
125 /* Round up `vector_bytes' to account for the alignment requirements
126 of an sbitmap. One could allocate the vector-table and set of sbitmaps
127 separately, but that requires maintaining two pointers or creating
128 a cover struct to hold both pointers (so our result is still just
129 one pointer). Neither is a bad idea, but this is simpler for now. */
131 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
132 struct { char x
; SBITMAP_ELT_TYPE y
; } align
;
133 int alignment
= (char *) & align
.y
- & align
.x
;
134 vector_bytes
= (vector_bytes
+ alignment
- 1) & ~ (alignment
- 1);
137 amt
= vector_bytes
+ (n_vecs
* elm_bytes
);
138 bitmap_vector
= (sbitmap
*) xmalloc (amt
);
140 for (i
= 0, offset
= vector_bytes
; i
< n_vecs
; i
++, offset
+= elm_bytes
)
142 sbitmap b
= (sbitmap
) ((char *) bitmap_vector
+ offset
);
144 bitmap_vector
[i
] = b
;
150 return bitmap_vector
;
153 /* Copy sbitmap SRC to DST. */
156 sbitmap_copy (dst
, src
)
159 memcpy (dst
->elms
, src
->elms
, sizeof (SBITMAP_ELT_TYPE
) * dst
->size
);
162 /* Determine if a == b. */
167 return !memcmp (a
->elms
, b
->elms
, sizeof (SBITMAP_ELT_TYPE
) * a
->size
);
170 /* Zero all elements in a bitmap. */
176 memset ((PTR
) bmap
->elms
, 0, bmap
->bytes
);
179 /* Set all elements in a bitmap to ones. */
185 unsigned int last_bit
;
187 memset ((PTR
) bmap
->elms
, -1, bmap
->bytes
);
189 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
191 bmap
->elms
[bmap
->size
- 1]
192 = (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
195 /* Zero a vector of N_VECS bitmaps. */
198 sbitmap_vector_zero (bmap
, n_vecs
)
204 for (i
= 0; i
< n_vecs
; i
++)
205 sbitmap_zero (bmap
[i
]);
208 /* Set a vector of N_VECS bitmaps to ones. */
211 sbitmap_vector_ones (bmap
, n_vecs
)
217 for (i
= 0; i
< n_vecs
; i
++)
218 sbitmap_ones (bmap
[i
]);
221 /* Set DST to be A union (B - C).
223 Returns true if any change is made. */
226 sbitmap_union_of_diff_cg (dst
, a
, b
, c
)
227 sbitmap dst
, a
, b
, c
;
229 unsigned int i
, n
= dst
->size
;
230 sbitmap_ptr dstp
= dst
->elms
;
231 sbitmap_ptr ap
= a
->elms
;
232 sbitmap_ptr bp
= b
->elms
;
233 sbitmap_ptr cp
= c
->elms
;
234 SBITMAP_ELT_TYPE changed
= 0;
236 for (i
= 0; i
< n
; i
++)
238 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & ~*cp
++);
239 changed
|= *dstp
^ tmp
;
247 sbitmap_union_of_diff (dst
, a
, b
, c
)
248 sbitmap dst
, a
, b
, c
;
250 unsigned int i
, n
= dst
->size
;
251 sbitmap_ptr dstp
= dst
->elms
;
252 sbitmap_ptr ap
= a
->elms
;
253 sbitmap_ptr bp
= b
->elms
;
254 sbitmap_ptr cp
= c
->elms
;
256 for (i
= 0; i
< n
; i
++)
257 *dstp
++ = *ap
++ | (*bp
++ & ~*cp
++);
260 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
263 sbitmap_not (dst
, src
)
266 unsigned int i
, n
= dst
->size
;
267 sbitmap_ptr dstp
= dst
->elms
;
268 sbitmap_ptr srcp
= src
->elms
;
270 for (i
= 0; i
< n
; i
++)
274 /* Set the bits in DST to be the difference between the bits
275 in A and the bits in B. i.e. dst = a & (~b). */
278 sbitmap_difference (dst
, a
, b
)
281 unsigned int i
, dst_size
= dst
->size
;
282 unsigned int min_size
= dst
->size
;
283 sbitmap_ptr dstp
= dst
->elms
;
284 sbitmap_ptr ap
= a
->elms
;
285 sbitmap_ptr bp
= b
->elms
;
287 /* A should be at least as large as DEST, to have a defined source. */
288 if (a
->size
< dst_size
)
290 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
291 only copy the subtrahend into dest. */
292 if (b
->size
< min_size
)
294 for (i
= 0; i
< min_size
; i
++)
295 *dstp
++ = *ap
++ & (~*bp
++);
296 /* Now fill the rest of dest from A, if B was too short.
297 This makes sense only when destination and A differ. */
298 if (dst
!= a
&& i
!= dst_size
)
299 for (; i
< dst_size
; i
++)
303 /* Set DST to be (A and B).
304 Return nonzero if any change is made. */
307 sbitmap_a_and_b_cg (dst
, a
, b
)
310 unsigned int i
, n
= dst
->size
;
311 sbitmap_ptr dstp
= dst
->elms
;
312 sbitmap_ptr ap
= a
->elms
;
313 sbitmap_ptr bp
= b
->elms
;
314 SBITMAP_ELT_TYPE changed
= 0;
316 for (i
= 0; i
< n
; i
++)
318 SBITMAP_ELT_TYPE tmp
= *ap
++ & *bp
++;
319 changed
= *dstp
^ tmp
;
327 sbitmap_a_and_b (dst
, a
, b
)
330 unsigned int i
, n
= dst
->size
;
331 sbitmap_ptr dstp
= dst
->elms
;
332 sbitmap_ptr ap
= a
->elms
;
333 sbitmap_ptr bp
= b
->elms
;
335 for (i
= 0; i
< n
; i
++)
336 *dstp
++ = *ap
++ & *bp
++;
339 /* Set DST to be (A xor B)).
340 Return nonzero if any change is made. */
343 sbitmap_a_xor_b_cg (dst
, a
, b
)
346 unsigned int i
, n
= dst
->size
;
347 sbitmap_ptr dstp
= dst
->elms
;
348 sbitmap_ptr ap
= a
->elms
;
349 sbitmap_ptr bp
= b
->elms
;
350 SBITMAP_ELT_TYPE changed
= 0;
352 for (i
= 0; i
< n
; i
++)
354 SBITMAP_ELT_TYPE tmp
= *ap
++ ^ *bp
++;
355 changed
= *dstp
^ tmp
;
363 sbitmap_a_xor_b (dst
, a
, b
)
366 unsigned int i
, n
= dst
->size
;
367 sbitmap_ptr dstp
= dst
->elms
;
368 sbitmap_ptr ap
= a
->elms
;
369 sbitmap_ptr bp
= b
->elms
;
371 for (i
= 0; i
< n
; i
++)
372 *dstp
++ = *ap
++ ^ *bp
++;
375 /* Set DST to be (A or B)).
376 Return nonzero if any change is made. */
379 sbitmap_a_or_b_cg (dst
, a
, b
)
382 unsigned int i
, n
= dst
->size
;
383 sbitmap_ptr dstp
= dst
->elms
;
384 sbitmap_ptr ap
= a
->elms
;
385 sbitmap_ptr bp
= b
->elms
;
386 SBITMAP_ELT_TYPE changed
= 0;
388 for (i
= 0; i
< n
; i
++)
390 SBITMAP_ELT_TYPE tmp
= *ap
++ | *bp
++;
391 changed
= *dstp
^ tmp
;
399 sbitmap_a_or_b (dst
, a
, b
)
402 unsigned int i
, n
= dst
->size
;
403 sbitmap_ptr dstp
= dst
->elms
;
404 sbitmap_ptr ap
= a
->elms
;
405 sbitmap_ptr bp
= b
->elms
;
407 for (i
= 0; i
< n
; i
++)
408 *dstp
++ = *ap
++ | *bp
++;
411 /* Return nonzero if A is a subset of B. */
414 sbitmap_a_subset_b_p (a
, b
)
417 unsigned int i
, n
= a
->size
;
420 for (ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< n
; i
++, ap
++, bp
++)
421 if ((*ap
| *bp
) != *bp
)
427 /* Set DST to be (A or (B and C)).
428 Return nonzero if any change is made. */
431 sbitmap_a_or_b_and_c_cg (dst
, a
, b
, c
)
432 sbitmap dst
, a
, b
, c
;
434 unsigned int i
, n
= dst
->size
;
435 sbitmap_ptr dstp
= dst
->elms
;
436 sbitmap_ptr ap
= a
->elms
;
437 sbitmap_ptr bp
= b
->elms
;
438 sbitmap_ptr cp
= c
->elms
;
439 SBITMAP_ELT_TYPE changed
= 0;
441 for (i
= 0; i
< n
; i
++)
443 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & *cp
++);
444 changed
|= *dstp
^ tmp
;
452 sbitmap_a_or_b_and_c (dst
, a
, b
, c
)
453 sbitmap dst
, a
, b
, c
;
455 unsigned int i
, n
= dst
->size
;
456 sbitmap_ptr dstp
= dst
->elms
;
457 sbitmap_ptr ap
= a
->elms
;
458 sbitmap_ptr bp
= b
->elms
;
459 sbitmap_ptr cp
= c
->elms
;
461 for (i
= 0; i
< n
; i
++)
462 *dstp
++ = *ap
++ | (*bp
++ & *cp
++);
465 /* Set DST to be (A and (B or C)).
466 Return nonzero if any change is made. */
469 sbitmap_a_and_b_or_c_cg (dst
, a
, b
, c
)
470 sbitmap dst
, a
, b
, c
;
472 unsigned int i
, n
= dst
->size
;
473 sbitmap_ptr dstp
= dst
->elms
;
474 sbitmap_ptr ap
= a
->elms
;
475 sbitmap_ptr bp
= b
->elms
;
476 sbitmap_ptr cp
= c
->elms
;
477 SBITMAP_ELT_TYPE changed
= 0;
479 for (i
= 0; i
< n
; i
++)
481 SBITMAP_ELT_TYPE tmp
= *ap
++ & (*bp
++ | *cp
++);
482 changed
|= *dstp
^ tmp
;
490 sbitmap_a_and_b_or_c (dst
, a
, b
, c
)
491 sbitmap dst
, a
, b
, c
;
493 unsigned int i
, n
= dst
->size
;
494 sbitmap_ptr dstp
= dst
->elms
;
495 sbitmap_ptr ap
= a
->elms
;
496 sbitmap_ptr bp
= b
->elms
;
497 sbitmap_ptr cp
= c
->elms
;
499 for (i
= 0; i
< n
; i
++)
500 *dstp
++ = *ap
++ & (*bp
++ | *cp
++);
504 /* Set the bitmap DST to the intersection of SRC of successors of
505 block number BB, using the new flow graph structures. */
508 sbitmap_intersection_of_succs (dst
, src
, bb
)
513 basic_block b
= BASIC_BLOCK (bb
);
514 unsigned int set_size
= dst
->size
;
517 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
519 if (e
->dest
== EXIT_BLOCK_PTR
)
522 sbitmap_copy (dst
, src
[e
->dest
->index
]);
529 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
534 if (e
->dest
== EXIT_BLOCK_PTR
)
537 p
= src
[e
->dest
->index
]->elms
;
539 for (i
= 0; i
< set_size
; i
++)
544 /* Set the bitmap DST to the intersection of SRC of predecessors of
545 block number BB, using the new flow graph structures. */
548 sbitmap_intersection_of_preds (dst
, src
, bb
)
553 basic_block b
= BASIC_BLOCK (bb
);
554 unsigned int set_size
= dst
->size
;
557 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
559 if (e
->src
== ENTRY_BLOCK_PTR
)
562 sbitmap_copy (dst
, src
[e
->src
->index
]);
569 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
574 if (e
->src
== ENTRY_BLOCK_PTR
)
577 p
= src
[e
->src
->index
]->elms
;
579 for (i
= 0; i
< set_size
; i
++)
584 /* Set the bitmap DST to the union of SRC of successors of
585 block number BB, using the new flow graph structures. */
588 sbitmap_union_of_succs (dst
, src
, bb
)
593 basic_block b
= BASIC_BLOCK (bb
);
594 unsigned int set_size
= dst
->size
;
597 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
599 if (e
->dest
== EXIT_BLOCK_PTR
)
602 sbitmap_copy (dst
, src
[e
->dest
->index
]);
609 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
614 if (e
->dest
== EXIT_BLOCK_PTR
)
617 p
= src
[e
->dest
->index
]->elms
;
619 for (i
= 0; i
< set_size
; i
++)
624 /* Set the bitmap DST to the union of SRC of predecessors of
625 block number BB, using the new flow graph structures. */
628 sbitmap_union_of_preds (dst
, src
, bb
)
633 basic_block b
= BASIC_BLOCK (bb
);
634 unsigned int set_size
= dst
->size
;
637 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
639 if (e
->src
== ENTRY_BLOCK_PTR
)
642 sbitmap_copy (dst
, src
[e
->src
->index
]);
649 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
654 if (e
->src
== ENTRY_BLOCK_PTR
)
657 p
= src
[e
->src
->index
]->elms
;
659 for (i
= 0; i
< set_size
; i
++)
665 /* Return number of first bit set in the bitmap, -1 if none. */
668 sbitmap_first_set_bit (bmap
)
673 EXECUTE_IF_SET_IN_SBITMAP (bmap
, 0, n
, { return n
; });
677 /* Return number of last bit set in the bitmap, -1 if none. */
680 sbitmap_last_set_bit (bmap
)
684 SBITMAP_ELT_TYPE
*ptr
= bmap
->elms
;
686 for (i
= bmap
->size
- 1; i
>= 0; i
--)
688 SBITMAP_ELT_TYPE word
= ptr
[i
];
692 unsigned int index
= (i
+ 1) * SBITMAP_ELT_BITS
- 1;
693 SBITMAP_ELT_TYPE mask
694 = (SBITMAP_ELT_TYPE
) 1 << (SBITMAP_ELT_BITS
- 1);
698 if ((word
& mask
) != 0)
711 dump_sbitmap (file
, bmap
)
715 unsigned int i
, n
, j
;
716 unsigned int set_size
= bmap
->size
;
717 unsigned int total_bits
= bmap
->n_bits
;
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
++)
723 if (n
!= 0 && n
% 10 == 0)
727 (bmap
->elms
[i
] & ((SBITMAP_ELT_TYPE
) 1 << j
)) != 0);
730 fprintf (file
, "\n");
734 dump_sbitmap_file (file
, bmap
)
740 fprintf (file
, "n_bits = %d, set = {", bmap
->n_bits
);
742 for (pos
= 30, i
= 0; i
< bmap
->n_bits
; i
++)
743 if (TEST_BIT (bmap
, i
))
747 fprintf (file
, "\n ");
751 fprintf (file
, "%d ", i
);
752 pos
+= 2 + (i
>= 10) + (i
>= 100) + (i
>= 1000);
755 fprintf (file
, "}\n");
762 dump_sbitmap_file (stderr
, bmap
);
766 dump_sbitmap_vector (file
, title
, subtitle
, bmaps
, n_maps
)
768 const char *title
, *subtitle
;
774 fprintf (file
, "%s\n", title
);
775 for (bb
= 0; bb
< n_maps
; bb
++)
777 fprintf (file
, "%s %d\n", subtitle
, bb
);
778 dump_sbitmap (file
, bmaps
[bb
]);
781 fprintf (file
, "\n");