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 (unsigned int n_elms
)
37 unsigned int bytes
, size
, amt
;
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
));
45 bmap
->n_bits
= n_elms
;
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. */
56 sbitmap_resize (sbitmap bmap
, unsigned int n_elms
, int def
)
58 unsigned int bytes
, size
, amt
;
59 unsigned int last_bit
;
61 size
= SBITMAP_SET_SIZE (n_elms
);
62 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
63 if (bytes
> bmap
->bytes
)
65 amt
= (sizeof (struct simple_bitmap_def
)
66 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
67 bmap
= xrealloc (bmap
, amt
);
70 if (n_elms
> bmap
->n_bits
)
74 memset (bmap
->elms
+ bmap
->size
, -1, bytes
- bmap
->bytes
);
76 /* Set the new bits if the original last element. */
77 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
79 bmap
->elms
[bmap
->size
- 1]
80 |= ~((SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
));
82 /* Clear the unused bit in the new last element. */
83 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
86 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
89 memset (bmap
->elms
+ bmap
->size
, 0, bytes
- bmap
->bytes
);
91 else if (n_elms
< bmap
->n_bits
)
93 /* Clear the surplus bits in the last word. */
94 last_bit
= n_elms
% SBITMAP_ELT_BITS
;
97 &= (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
100 bmap
->n_bits
= n_elms
;
106 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
109 sbitmap_vector_alloc (unsigned int n_vecs
, unsigned int n_elms
)
111 unsigned int i
, bytes
, offset
, elm_bytes
, size
, amt
, vector_bytes
;
112 sbitmap
*bitmap_vector
;
114 size
= SBITMAP_SET_SIZE (n_elms
);
115 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
116 elm_bytes
= (sizeof (struct simple_bitmap_def
)
117 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
118 vector_bytes
= n_vecs
* sizeof (sbitmap
*);
120 /* Round up `vector_bytes' to account for the alignment requirements
121 of an sbitmap. One could allocate the vector-table and set of sbitmaps
122 separately, but that requires maintaining two pointers or creating
123 a cover struct to hold both pointers (so our result is still just
124 one pointer). Neither is a bad idea, but this is simpler for now. */
126 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
127 struct { char x
; SBITMAP_ELT_TYPE y
; } align
;
128 int alignment
= (char *) & align
.y
- & align
.x
;
129 vector_bytes
= (vector_bytes
+ alignment
- 1) & ~ (alignment
- 1);
132 amt
= vector_bytes
+ (n_vecs
* elm_bytes
);
133 bitmap_vector
= xmalloc (amt
);
135 for (i
= 0, offset
= vector_bytes
; i
< n_vecs
; i
++, offset
+= elm_bytes
)
137 sbitmap b
= (sbitmap
) ((char *) bitmap_vector
+ offset
);
139 bitmap_vector
[i
] = b
;
145 return bitmap_vector
;
148 /* Copy sbitmap SRC to DST. */
151 sbitmap_copy (sbitmap dst
, sbitmap src
)
153 memcpy (dst
->elms
, src
->elms
, sizeof (SBITMAP_ELT_TYPE
) * dst
->size
);
156 /* Determine if a == b. */
158 sbitmap_equal (sbitmap a
, sbitmap b
)
160 return !memcmp (a
->elms
, b
->elms
, sizeof (SBITMAP_ELT_TYPE
) * a
->size
);
163 /* Zero all elements in a bitmap. */
166 sbitmap_zero (sbitmap bmap
)
168 memset (bmap
->elms
, 0, bmap
->bytes
);
171 /* Set all elements in a bitmap to ones. */
174 sbitmap_ones (sbitmap bmap
)
176 unsigned int last_bit
;
178 memset (bmap
->elms
, -1, bmap
->bytes
);
180 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
182 bmap
->elms
[bmap
->size
- 1]
183 = (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
186 /* Zero a vector of N_VECS bitmaps. */
189 sbitmap_vector_zero (sbitmap
*bmap
, unsigned int n_vecs
)
193 for (i
= 0; i
< n_vecs
; i
++)
194 sbitmap_zero (bmap
[i
]);
197 /* Set a vector of N_VECS bitmaps to ones. */
200 sbitmap_vector_ones (sbitmap
*bmap
, unsigned int n_vecs
)
204 for (i
= 0; i
< n_vecs
; i
++)
205 sbitmap_ones (bmap
[i
]);
208 /* Set DST to be A union (B - C).
210 Returns true if any change is made. */
213 sbitmap_union_of_diff_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
215 unsigned int i
, n
= dst
->size
;
216 sbitmap_ptr dstp
= dst
->elms
;
217 sbitmap_ptr ap
= a
->elms
;
218 sbitmap_ptr bp
= b
->elms
;
219 sbitmap_ptr cp
= c
->elms
;
220 SBITMAP_ELT_TYPE changed
= 0;
222 for (i
= 0; i
< n
; i
++)
224 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & ~*cp
++);
225 changed
|= *dstp
^ tmp
;
233 sbitmap_union_of_diff (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
235 unsigned int i
, n
= dst
->size
;
236 sbitmap_ptr dstp
= dst
->elms
;
237 sbitmap_ptr ap
= a
->elms
;
238 sbitmap_ptr bp
= b
->elms
;
239 sbitmap_ptr cp
= c
->elms
;
241 for (i
= 0; i
< n
; i
++)
242 *dstp
++ = *ap
++ | (*bp
++ & ~*cp
++);
245 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
248 sbitmap_not (sbitmap dst
, sbitmap src
)
250 unsigned int i
, n
= dst
->size
;
251 sbitmap_ptr dstp
= dst
->elms
;
252 sbitmap_ptr srcp
= src
->elms
;
254 for (i
= 0; i
< n
; i
++)
258 /* Set the bits in DST to be the difference between the bits
259 in A and the bits in B. i.e. dst = a & (~b). */
262 sbitmap_difference (sbitmap dst
, sbitmap a
, sbitmap b
)
264 unsigned int i
, dst_size
= dst
->size
;
265 unsigned int min_size
= dst
->size
;
266 sbitmap_ptr dstp
= dst
->elms
;
267 sbitmap_ptr ap
= a
->elms
;
268 sbitmap_ptr bp
= b
->elms
;
270 /* A should be at least as large as DEST, to have a defined source. */
271 if (a
->size
< dst_size
)
273 /* If minuend is smaller, we simply pretend it to be zero bits, i.e.
274 only copy the subtrahend into dest. */
275 if (b
->size
< min_size
)
277 for (i
= 0; i
< min_size
; i
++)
278 *dstp
++ = *ap
++ & (~*bp
++);
279 /* Now fill the rest of dest from A, if B was too short.
280 This makes sense only when destination and A differ. */
281 if (dst
!= a
&& i
!= dst_size
)
282 for (; i
< dst_size
; i
++)
286 /* Set DST to be (A and B).
287 Return nonzero if any change is made. */
290 sbitmap_a_and_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
292 unsigned int i
, n
= dst
->size
;
293 sbitmap_ptr dstp
= dst
->elms
;
294 sbitmap_ptr ap
= a
->elms
;
295 sbitmap_ptr bp
= b
->elms
;
296 SBITMAP_ELT_TYPE changed
= 0;
298 for (i
= 0; i
< n
; i
++)
300 SBITMAP_ELT_TYPE tmp
= *ap
++ & *bp
++;
301 changed
= *dstp
^ tmp
;
309 sbitmap_a_and_b (sbitmap dst
, sbitmap a
, sbitmap b
)
311 unsigned int i
, n
= dst
->size
;
312 sbitmap_ptr dstp
= dst
->elms
;
313 sbitmap_ptr ap
= a
->elms
;
314 sbitmap_ptr bp
= b
->elms
;
316 for (i
= 0; i
< n
; i
++)
317 *dstp
++ = *ap
++ & *bp
++;
320 /* Set DST to be (A xor B)).
321 Return nonzero if any change is made. */
324 sbitmap_a_xor_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
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_ELT_TYPE changed
= 0;
332 for (i
= 0; i
< n
; i
++)
334 SBITMAP_ELT_TYPE tmp
= *ap
++ ^ *bp
++;
335 changed
= *dstp
^ tmp
;
343 sbitmap_a_xor_b (sbitmap dst
, sbitmap a
, sbitmap b
)
345 unsigned int i
, n
= dst
->size
;
346 sbitmap_ptr dstp
= dst
->elms
;
347 sbitmap_ptr ap
= a
->elms
;
348 sbitmap_ptr bp
= b
->elms
;
350 for (i
= 0; i
< n
; i
++)
351 *dstp
++ = *ap
++ ^ *bp
++;
354 /* Set DST to be (A or B)).
355 Return nonzero if any change is made. */
358 sbitmap_a_or_b_cg (sbitmap dst
, sbitmap a
, sbitmap b
)
360 unsigned int i
, n
= dst
->size
;
361 sbitmap_ptr dstp
= dst
->elms
;
362 sbitmap_ptr ap
= a
->elms
;
363 sbitmap_ptr bp
= b
->elms
;
364 SBITMAP_ELT_TYPE changed
= 0;
366 for (i
= 0; i
< n
; i
++)
368 SBITMAP_ELT_TYPE tmp
= *ap
++ | *bp
++;
369 changed
= *dstp
^ tmp
;
377 sbitmap_a_or_b (sbitmap dst
, sbitmap a
, sbitmap b
)
379 unsigned int i
, n
= dst
->size
;
380 sbitmap_ptr dstp
= dst
->elms
;
381 sbitmap_ptr ap
= a
->elms
;
382 sbitmap_ptr bp
= b
->elms
;
384 for (i
= 0; i
< n
; i
++)
385 *dstp
++ = *ap
++ | *bp
++;
388 /* Return nonzero if A is a subset of B. */
391 sbitmap_a_subset_b_p (sbitmap a
, sbitmap b
)
393 unsigned int i
, n
= a
->size
;
396 for (ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< n
; i
++, ap
++, bp
++)
397 if ((*ap
| *bp
) != *bp
)
403 /* Set DST to be (A or (B and C)).
404 Return nonzero if any change is made. */
407 sbitmap_a_or_b_and_c_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
409 unsigned int i
, n
= dst
->size
;
410 sbitmap_ptr dstp
= dst
->elms
;
411 sbitmap_ptr ap
= a
->elms
;
412 sbitmap_ptr bp
= b
->elms
;
413 sbitmap_ptr cp
= c
->elms
;
414 SBITMAP_ELT_TYPE changed
= 0;
416 for (i
= 0; i
< n
; i
++)
418 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & *cp
++);
419 changed
|= *dstp
^ tmp
;
427 sbitmap_a_or_b_and_c (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
429 unsigned int i
, n
= dst
->size
;
430 sbitmap_ptr dstp
= dst
->elms
;
431 sbitmap_ptr ap
= a
->elms
;
432 sbitmap_ptr bp
= b
->elms
;
433 sbitmap_ptr cp
= c
->elms
;
435 for (i
= 0; i
< n
; i
++)
436 *dstp
++ = *ap
++ | (*bp
++ & *cp
++);
439 /* Set DST to be (A and (B or C)).
440 Return nonzero if any change is made. */
443 sbitmap_a_and_b_or_c_cg (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
445 unsigned int i
, n
= dst
->size
;
446 sbitmap_ptr dstp
= dst
->elms
;
447 sbitmap_ptr ap
= a
->elms
;
448 sbitmap_ptr bp
= b
->elms
;
449 sbitmap_ptr cp
= c
->elms
;
450 SBITMAP_ELT_TYPE changed
= 0;
452 for (i
= 0; i
< n
; i
++)
454 SBITMAP_ELT_TYPE tmp
= *ap
++ & (*bp
++ | *cp
++);
455 changed
|= *dstp
^ tmp
;
463 sbitmap_a_and_b_or_c (sbitmap dst
, sbitmap a
, sbitmap b
, sbitmap c
)
465 unsigned int i
, n
= dst
->size
;
466 sbitmap_ptr dstp
= dst
->elms
;
467 sbitmap_ptr ap
= a
->elms
;
468 sbitmap_ptr bp
= b
->elms
;
469 sbitmap_ptr cp
= c
->elms
;
471 for (i
= 0; i
< n
; i
++)
472 *dstp
++ = *ap
++ & (*bp
++ | *cp
++);
476 /* Set the bitmap DST to the intersection of SRC of successors of
477 block number BB, using the new flow graph structures. */
480 sbitmap_intersection_of_succs (sbitmap dst
, sbitmap
*src
, int bb
)
482 basic_block b
= BASIC_BLOCK (bb
);
483 unsigned int set_size
= dst
->size
;
486 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
488 if (e
->dest
== EXIT_BLOCK_PTR
)
491 sbitmap_copy (dst
, src
[e
->dest
->index
]);
498 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
503 if (e
->dest
== EXIT_BLOCK_PTR
)
506 p
= src
[e
->dest
->index
]->elms
;
508 for (i
= 0; i
< set_size
; i
++)
513 /* Set the bitmap DST to the intersection of SRC of predecessors of
514 block number BB, using the new flow graph structures. */
517 sbitmap_intersection_of_preds (sbitmap dst
, sbitmap
*src
, int bb
)
519 basic_block b
= BASIC_BLOCK (bb
);
520 unsigned int set_size
= dst
->size
;
523 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
525 if (e
->src
== ENTRY_BLOCK_PTR
)
528 sbitmap_copy (dst
, src
[e
->src
->index
]);
535 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
540 if (e
->src
== ENTRY_BLOCK_PTR
)
543 p
= src
[e
->src
->index
]->elms
;
545 for (i
= 0; i
< set_size
; i
++)
550 /* Set the bitmap DST to the union of SRC of successors of
551 block number BB, using the new flow graph structures. */
554 sbitmap_union_of_succs (sbitmap dst
, sbitmap
*src
, int bb
)
556 basic_block b
= BASIC_BLOCK (bb
);
557 unsigned int set_size
= dst
->size
;
560 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
562 if (e
->dest
== EXIT_BLOCK_PTR
)
565 sbitmap_copy (dst
, src
[e
->dest
->index
]);
572 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
577 if (e
->dest
== EXIT_BLOCK_PTR
)
580 p
= src
[e
->dest
->index
]->elms
;
582 for (i
= 0; i
< set_size
; i
++)
587 /* Set the bitmap DST to the union of SRC of predecessors of
588 block number BB, using the new flow graph structures. */
591 sbitmap_union_of_preds (sbitmap dst
, sbitmap
*src
, int bb
)
593 basic_block b
= BASIC_BLOCK (bb
);
594 unsigned int set_size
= dst
->size
;
597 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
599 if (e
->src
== ENTRY_BLOCK_PTR
)
602 sbitmap_copy (dst
, src
[e
->src
->index
]);
609 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
614 if (e
->src
== ENTRY_BLOCK_PTR
)
617 p
= src
[e
->src
->index
]->elms
;
619 for (i
= 0; i
< set_size
; i
++)
625 /* Return number of first bit set in the bitmap, -1 if none. */
628 sbitmap_first_set_bit (sbitmap bmap
)
632 EXECUTE_IF_SET_IN_SBITMAP (bmap
, 0, n
, { return n
; });
636 /* Return number of last bit set in the bitmap, -1 if none. */
639 sbitmap_last_set_bit (sbitmap bmap
)
642 SBITMAP_ELT_TYPE
*ptr
= bmap
->elms
;
644 for (i
= bmap
->size
- 1; i
>= 0; i
--)
646 SBITMAP_ELT_TYPE word
= ptr
[i
];
650 unsigned int index
= (i
+ 1) * SBITMAP_ELT_BITS
- 1;
651 SBITMAP_ELT_TYPE mask
652 = (SBITMAP_ELT_TYPE
) 1 << (SBITMAP_ELT_BITS
- 1);
656 if ((word
& mask
) != 0)
669 dump_sbitmap (FILE *file
, sbitmap bmap
)
671 unsigned int i
, n
, j
;
672 unsigned int set_size
= bmap
->size
;
673 unsigned int total_bits
= bmap
->n_bits
;
676 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
677 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
679 if (n
!= 0 && n
% 10 == 0)
683 (bmap
->elms
[i
] & ((SBITMAP_ELT_TYPE
) 1 << j
)) != 0);
686 fprintf (file
, "\n");
690 dump_sbitmap_file (FILE *file
, sbitmap bmap
)
694 fprintf (file
, "n_bits = %d, set = {", bmap
->n_bits
);
696 for (pos
= 30, i
= 0; i
< bmap
->n_bits
; i
++)
697 if (TEST_BIT (bmap
, i
))
701 fprintf (file
, "\n ");
705 fprintf (file
, "%d ", i
);
706 pos
+= 2 + (i
>= 10) + (i
>= 100) + (i
>= 1000);
709 fprintf (file
, "}\n");
713 debug_sbitmap (sbitmap bmap
)
715 dump_sbitmap_file (stderr
, bmap
);
719 dump_sbitmap_vector (FILE *file
, const char *title
, const char *subtitle
,
720 sbitmap
*bmaps
, int n_maps
)
724 fprintf (file
, "%s\n", title
);
725 for (bb
= 0; bb
< n_maps
; bb
++)
727 fprintf (file
, "%s %d\n", subtitle
, bb
);
728 dump_sbitmap (file
, bmaps
[bb
]);
731 fprintf (file
, "\n");