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 memset (bmap
->elms
, -1, bmap
->bytes
);
121 /* Zero a vector of N_VECS bitmaps. */
124 sbitmap_vector_zero (bmap
, n_vecs
)
130 for (i
= 0; i
< n_vecs
; i
++)
131 sbitmap_zero (bmap
[i
]);
134 /* Set to ones a vector of N_VECS bitmaps. */
137 sbitmap_vector_ones (bmap
, n_vecs
)
143 for (i
= 0; i
< n_vecs
; i
++)
144 sbitmap_ones (bmap
[i
]);
147 /* Set DST to be A union (B - C).
149 Return non-zero if any change is made. */
152 sbitmap_union_of_diff (dst
, a
, b
, c
)
153 sbitmap dst
, a
, b
, c
;
156 sbitmap_ptr dstp
, ap
, bp
, cp
;
163 for (i
= 0; i
< dst
->size
; i
++)
165 SBITMAP_ELT_TYPE tmp
= *ap
| (*bp
& ~*cp
);
169 dstp
++; ap
++; bp
++; cp
++;
174 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
177 sbitmap_not (dst
, src
)
181 sbitmap_ptr dstp
, ap
;
185 for (i
= 0; i
< dst
->size
; i
++)
187 SBITMAP_ELT_TYPE tmp
= ~(*ap
);
193 /* Set the bits in DST to be the difference between the bits
194 in A and the bits in B. i.e. dst = a - b.
195 The - operator is implemented as a & (~b). */
198 sbitmap_difference (dst
, a
, b
)
202 sbitmap_ptr dstp
, ap
, bp
;
207 for (i
= 0; i
< dst
->size
; i
++)
208 *dstp
++ = *ap
++ & (~*bp
++);
211 /* Set DST to be (A and B)).
212 Return non-zero if any change is made. */
215 sbitmap_a_and_b (dst
, a
, b
)
219 sbitmap_ptr dstp
, ap
, bp
;
225 for (i
= 0; i
< dst
->size
; i
++)
227 SBITMAP_ELT_TYPE tmp
= *ap
& *bp
;
235 /* Set DST to be (A or B)).
236 Return non-zero if any change is made. */
239 sbitmap_a_or_b (dst
, a
, b
)
243 sbitmap_ptr dstp
, ap
, bp
;
249 for (i
= 0; i
< dst
->size
; i
++)
251 SBITMAP_ELT_TYPE tmp
= *ap
| *bp
;
260 /* Set DST to be (A or (B and C)).
261 Return non-zero if any change is made. */
264 sbitmap_a_or_b_and_c (dst
, a
, b
, c
)
265 sbitmap dst
, a
, b
, c
;
268 sbitmap_ptr dstp
, ap
, bp
, cp
;
275 for (i
= 0; i
< dst
->size
; i
++)
277 SBITMAP_ELT_TYPE tmp
= *ap
| (*bp
& *cp
);
281 dstp
++; ap
++; bp
++; cp
++;
286 /* Set DST to be (A ann (B or C)).
287 Return non-zero if any change is made. */
290 sbitmap_a_and_b_or_c (dst
, a
, b
, c
)
291 sbitmap dst
, a
, b
, c
;
294 sbitmap_ptr dstp
, ap
, bp
, cp
;
301 for (i
= 0; i
< dst
->size
; i
++)
303 SBITMAP_ELT_TYPE tmp
= *ap
& (*bp
| *cp
);
307 dstp
++; ap
++; bp
++; cp
++;
312 /* Set the bitmap DST to the intersection of SRC of all predecessors or
313 successors of block number BB (PRED_SUCC says which). */
316 sbitmap_intersect_of_predsucc (dst
, src
, bb
, pred_succ
)
320 int_list_ptr
*pred_succ
;
324 int set_size
= dst
->size
;
328 /* It is possible that there are no predecessors(/successors).
329 This can happen for example in unreachable code. */
333 /* In APL-speak this is the `and' reduction of the empty set and thus
334 the result is the identity for `and'. */
339 /* Set result to first predecessor/successor. */
341 for ( ; ps
!= NULL
; ps
= ps
->next
)
343 ps_bb
= INT_LIST_VAL (ps
);
344 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
346 sbitmap_copy (dst
, src
[ps_bb
]);
347 /* Break out since we're only doing first predecessor. */
353 /* Now do the remaining predecessors/successors. */
355 for (ps
= ps
->next
; ps
!= NULL
; ps
= ps
->next
)
360 ps_bb
= INT_LIST_VAL (ps
);
361 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
364 p
= src
[ps_bb
]->elms
;
367 for (i
= 0; i
< set_size
; i
++)
372 /* Set the bitmap DST to the union of SRC of all predecessors/successors of
376 sbitmap_union_of_predsucc (dst
, src
, bb
, pred_succ
)
380 int_list_ptr
*pred_succ
;
384 int set_size
= dst
->size
;
388 /* It is possible that there are no predecessors(/successors).
389 This can happen for example in unreachable code. */
393 /* In APL-speak this is the `or' reduction of the empty set and thus
394 the result is the identity for `or'. */
399 /* Set result to first predecessor/successor. */
401 for ( ; ps
!= NULL
; ps
= ps
->next
)
403 ps_bb
= INT_LIST_VAL (ps
);
404 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
406 sbitmap_copy (dst
, src
[ps_bb
]);
407 /* Break out since we're only doing first predecessor. */
413 /* Now do the remaining predecessors/successors. */
415 for (ps
= ps
->next
; ps
!= NULL
; ps
= ps
->next
)
420 ps_bb
= INT_LIST_VAL (ps
);
421 if (ps_bb
== ENTRY_BLOCK
|| ps_bb
== EXIT_BLOCK
)
424 p
= src
[ps_bb
]->elms
;
427 for (i
= 0; i
< set_size
; i
++)
433 dump_sbitmap (file
, bmap
)
438 int set_size
= bmap
->size
;
439 int total_bits
= bmap
->n_bits
;
442 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
444 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
446 if (n
!= 0 && n
% 10 == 0)
448 fprintf (file
, "%d", (bmap
->elms
[i
] & (1L << j
)) != 0);
451 fprintf (file
, "\n");
455 dump_sbitmap_vector (file
, title
, subtitle
, bmaps
, n_maps
)
457 char *title
, *subtitle
;
463 fprintf (file
, "%s\n", title
);
464 for (bb
= 0; bb
< n_maps
; bb
++)
466 fprintf (file
, "%s %d\n", subtitle
, bb
);
467 dump_sbitmap (file
, bmaps
[bb
]);
469 fprintf (file
, "\n");