2 Copyright (C) 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
25 #include "basic-block.h"
27 /* Bitmap manipulation routines. */
29 /* Allocate a simple bitmap of N_ELMS bits. */
32 sbitmap_alloc (n_elms
)
38 size
= SBITMAP_SET_SIZE (n_elms
);
39 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
40 amt
= (sizeof (struct simple_bitmap_def
)
41 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
42 bmap
= (sbitmap
) xmalloc (amt
);
43 bmap
->n_bits
= n_elms
;
49 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */
52 sbitmap_vector_alloc (n_vecs
, n_elms
)
55 int i
, bytes
, offset
, elm_bytes
, size
, amt
, vector_bytes
;
56 sbitmap
*bitmap_vector
;
58 size
= SBITMAP_SET_SIZE (n_elms
);
59 bytes
= size
* sizeof (SBITMAP_ELT_TYPE
);
60 elm_bytes
= (sizeof (struct simple_bitmap_def
)
61 + bytes
- sizeof (SBITMAP_ELT_TYPE
));
62 vector_bytes
= n_vecs
* sizeof (sbitmap
*);
64 /* Round up `vector_bytes' to account for the alignment requirements
65 of an sbitmap. One could allocate the vector-table and set of sbitmaps
66 separately, but that requires maintaining two pointers or creating
67 a cover struct to hold both pointers (so our result is still just
68 one pointer). Neither is a bad idea, but this is simpler for now. */
70 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */
71 struct { char x
; SBITMAP_ELT_TYPE y
; } align
;
72 int alignment
= (char *) & align
.y
- & align
.x
;
73 vector_bytes
= (vector_bytes
+ alignment
- 1) & ~ (alignment
- 1);
76 amt
= vector_bytes
+ (n_vecs
* elm_bytes
);
77 bitmap_vector
= (sbitmap
*) xmalloc (amt
);
79 for (i
= 0, offset
= vector_bytes
;
81 i
++, offset
+= elm_bytes
)
83 sbitmap b
= (sbitmap
) ((char *) bitmap_vector
+ offset
);
93 /* Copy sbitmap SRC to DST. */
96 sbitmap_copy (dst
, src
)
99 bcopy ((PTR
) src
->elms
, (PTR
) dst
->elms
,
100 sizeof (SBITMAP_ELT_TYPE
) * dst
->size
);
103 /* Zero all elements in a bitmap. */
109 bzero ((char *) bmap
->elms
, bmap
->bytes
);
112 /* Set to ones all elements in a bitmap. */
118 unsigned int last_bit
;
120 memset (bmap
->elms
, -1, bmap
->bytes
);
122 last_bit
= bmap
->n_bits
% (unsigned) SBITMAP_ELT_BITS
;
125 bmap
->elms
[bmap
->size
- 1]
126 = (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
130 /* Zero a vector of N_VECS bitmaps. */
133 sbitmap_vector_zero (bmap
, n_vecs
)
139 for (i
= 0; i
< n_vecs
; i
++)
140 sbitmap_zero (bmap
[i
]);
143 /* Set to ones a vector of N_VECS bitmaps. */
146 sbitmap_vector_ones (bmap
, n_vecs
)
152 for (i
= 0; i
< n_vecs
; i
++)
153 sbitmap_ones (bmap
[i
]);
156 /* Set DST to be A union (B - C).
158 Return non-zero if any change is made. */
161 sbitmap_union_of_diff (dst
, a
, b
, c
)
162 sbitmap dst
, a
, b
, c
;
165 sbitmap_ptr dstp
, ap
, bp
, cp
;
172 for (i
= 0; i
< dst
->size
; i
++)
174 SBITMAP_ELT_TYPE tmp
= *ap
| (*bp
& ~*cp
);
178 dstp
++; ap
++; bp
++; cp
++;
183 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
186 sbitmap_not (dst
, src
)
190 sbitmap_ptr dstp
, ap
;
194 for (i
= 0; i
< dst
->size
; i
++)
196 SBITMAP_ELT_TYPE tmp
= ~(*ap
);
202 /* Set the bits in DST to be the difference between the bits
203 in A and the bits in B. i.e. dst = a - b.
204 The - operator is implemented as a & (~b). */
207 sbitmap_difference (dst
, a
, b
)
211 sbitmap_ptr dstp
, ap
, bp
;
216 for (i
= 0; i
< dst
->size
; i
++)
217 *dstp
++ = *ap
++ & (~*bp
++);
220 /* Set DST to be (A and B).
221 Return non-zero if any change is made. */
224 sbitmap_a_and_b (dst
, a
, b
)
228 sbitmap_ptr dstp
, ap
, bp
;
234 for (i
= 0; i
< dst
->size
; i
++)
236 SBITMAP_ELT_TYPE tmp
= *ap
& *bp
;
244 /* Set DST to be (A or B)).
245 Return non-zero if any change is made. */
248 sbitmap_a_or_b (dst
, a
, b
)
252 sbitmap_ptr dstp
, ap
, bp
;
258 for (i
= 0; i
< dst
->size
; i
++)
260 SBITMAP_ELT_TYPE tmp
= *ap
| *bp
;
269 /* Set DST to be (A or (B and C)).
270 Return non-zero if any change is made. */
273 sbitmap_a_or_b_and_c (dst
, a
, b
, c
)
274 sbitmap dst
, a
, b
, c
;
277 sbitmap_ptr dstp
, ap
, bp
, cp
;
284 for (i
= 0; i
< dst
->size
; i
++)
286 SBITMAP_ELT_TYPE tmp
= *ap
| (*bp
& *cp
);
290 dstp
++; ap
++; bp
++; cp
++;
295 /* Set DST to be (A ann (B or C)).
296 Return non-zero if any change is made. */
299 sbitmap_a_and_b_or_c (dst
, a
, b
, c
)
300 sbitmap dst
, a
, b
, c
;
303 sbitmap_ptr dstp
, ap
, bp
, cp
;
310 for (i
= 0; i
< dst
->size
; i
++)
312 SBITMAP_ELT_TYPE tmp
= *ap
& (*bp
| *cp
);
316 dstp
++; ap
++; bp
++; cp
++;
321 /* Set the bitmap DST to the intersection of SRC of all predecessors or
322 successors of block number BB (PRED_SUCC says which). */
325 sbitmap_intersect_of_predsucc (dst
, src
, bb
, pred_succ
)
329 int_list_ptr
*pred_succ
;
333 int set_size
= dst
->size
;
337 /* It is possible that there are no predecessors(/successors).
338 This can happen for example in unreachable code. */
342 /* In APL-speak this is the `and' reduction of the empty set and thus
343 the result is the identity for `and'. */
348 /* Set result to first predecessor/successor. */
350 for ( ; ps
!= NULL
; ps
= ps
->next
)
352 ps_bb
= INT_LIST_VAL (ps
);
353 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
355 sbitmap_copy (dst
, src
[ps_bb
]);
356 /* Break out since we're only doing first predecessor. */
362 /* Now do the remaining predecessors/successors. */
364 for (ps
= ps
->next
; ps
!= NULL
; ps
= ps
->next
)
369 ps_bb
= INT_LIST_VAL (ps
);
370 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
373 p
= src
[ps_bb
]->elms
;
376 for (i
= 0; i
< set_size
; i
++)
381 /* Set the bitmap DST to the union of SRC of all predecessors/successors of
385 sbitmap_union_of_predsucc (dst
, src
, bb
, pred_succ
)
389 int_list_ptr
*pred_succ
;
393 int set_size
= dst
->size
;
397 /* It is possible that there are no predecessors(/successors).
398 This can happen for example in unreachable code. */
402 /* In APL-speak this is the `or' reduction of the empty set and thus
403 the result is the identity for `or'. */
408 /* Set result to first predecessor/successor. */
410 for ( ; ps
!= NULL
; ps
= ps
->next
)
412 ps_bb
= INT_LIST_VAL (ps
);
413 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
415 sbitmap_copy (dst
, src
[ps_bb
]);
416 /* Break out since we're only doing first predecessor. */
422 /* Now do the remaining predecessors/successors. */
424 for (ps
= ps
->next
; ps
!= NULL
; ps
= ps
->next
)
429 ps_bb
= INT_LIST_VAL (ps
);
430 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
433 p
= src
[ps_bb
]->elms
;
436 for (i
= 0; i
< set_size
; i
++)
441 /* Set the bitmap DST to the intersection of SRC of successors of
442 block number BB, using the new flow graph structures. */
445 sbitmap_intersection_of_succs (dst
, src
, bb
)
450 basic_block b
= BASIC_BLOCK (bb
);
452 int set_size
= dst
->size
;
454 for ( ; e
!= NULL
; e
= e
->succ_next
)
456 if (e
->dest
== EXIT_BLOCK_PTR
)
458 sbitmap_copy (dst
, src
[e
->dest
->index
]);
465 for ( e
= e
->succ_next
; e
!= NULL
; e
= e
->succ_next
)
470 if (e
->dest
== EXIT_BLOCK_PTR
)
473 p
= src
[e
->dest
->index
]->elms
;
475 for (i
= 0; i
< set_size
; i
++)
481 /* Set the bitmap DST to the intersection of SRC of predecessors of
482 block number BB, using the new flow graph structures. */
485 sbitmap_intersection_of_preds (dst
, src
, bb
)
490 basic_block b
= BASIC_BLOCK (bb
);
492 int set_size
= dst
->size
;
494 for ( ; e
!= NULL
; e
= e
->pred_next
)
496 if (e
->src
== ENTRY_BLOCK_PTR
)
498 sbitmap_copy (dst
, src
[e
->src
->index
]);
505 for ( e
= e
->pred_next
; e
!= NULL
; e
= e
->pred_next
)
510 if (e
->src
== ENTRY_BLOCK_PTR
)
513 p
= src
[e
->src
->index
]->elms
;
515 for (i
= 0; i
< set_size
; i
++)
521 /* Set the bitmap DST to the union of SRC of successors of
522 block number BB, using the new flow graph structures. */
525 sbitmap_union_of_succs (dst
, src
, bb
)
530 basic_block b
= BASIC_BLOCK (bb
);
532 int set_size
= dst
->size
;
534 for ( ; e
!= NULL
; e
= e
->succ_next
)
536 if (e
->dest
== EXIT_BLOCK_PTR
)
538 sbitmap_copy (dst
, src
[e
->dest
->index
]);
545 for ( e
= e
->succ_next
; e
!= NULL
; e
= e
->succ_next
)
550 if (e
->dest
== EXIT_BLOCK_PTR
)
553 p
= src
[e
->dest
->index
]->elms
;
555 for (i
= 0; i
< set_size
; i
++)
561 /* Set the bitmap DST to the union of SRC of predecessors of
562 block number BB, using the new flow graph structures. */
565 sbitmap_union_of_preds (dst
, src
, bb
)
570 basic_block b
= BASIC_BLOCK (bb
);
572 int set_size
= dst
->size
;
574 for ( ; e
!= NULL
; e
= e
->pred_next
)
576 if (e
->src
== ENTRY_BLOCK_PTR
)
578 sbitmap_copy (dst
, src
[e
->src
->index
]);
585 for ( e
= e
->pred_next
; e
!= NULL
; e
= e
->pred_next
)
590 if (e
->src
== ENTRY_BLOCK_PTR
)
593 p
= src
[e
->src
->index
]->elms
;
595 for (i
= 0; i
< set_size
; i
++)
602 dump_sbitmap (file
, bmap
)
607 int set_size
= bmap
->size
;
608 int total_bits
= bmap
->n_bits
;
611 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
613 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
615 if (n
!= 0 && n
% 10 == 0)
617 fprintf (file
, "%d", (bmap
->elms
[i
] & (1L << j
)) != 0);
620 fprintf (file
, "\n");
624 dump_sbitmap_vector (file
, title
, subtitle
, bmaps
, n_maps
)
626 const char *title
, *subtitle
;
632 fprintf (file
, "%s\n", title
);
633 for (bb
= 0; bb
< n_maps
; bb
++)
635 fprintf (file
, "%s %d\n", subtitle
, bb
);
636 dump_sbitmap (file
, bmaps
[bb
]);
638 fprintf (file
, "\n");