]>
gcc.gnu.org Git - gcc.git/blob - gcc/sbitmap.c
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
;
268 /* Return non-zero if A is a subset of B. */
271 sbitmap_a_subset_b_p (a
, b
)
279 for (i
= 0; i
< a
->size
; i
++)
281 if ((*ap
| *bp
) != *bp
)
288 /* Set DST to be (A or (B and C)).
289 Return non-zero if any change is made. */
292 sbitmap_a_or_b_and_c (dst
, a
, b
, c
)
293 sbitmap dst
, a
, b
, c
;
296 sbitmap_ptr dstp
, ap
, bp
, cp
;
303 for (i
= 0; i
< dst
->size
; i
++)
305 SBITMAP_ELT_TYPE tmp
= *ap
| (*bp
& *cp
);
309 dstp
++; ap
++; bp
++; cp
++;
314 /* Set DST to be (A ann (B or C)).
315 Return non-zero if any change is made. */
318 sbitmap_a_and_b_or_c (dst
, a
, b
, c
)
319 sbitmap dst
, a
, b
, c
;
322 sbitmap_ptr dstp
, ap
, bp
, cp
;
329 for (i
= 0; i
< dst
->size
; i
++)
331 SBITMAP_ELT_TYPE tmp
= *ap
& (*bp
| *cp
);
335 dstp
++; ap
++; bp
++; cp
++;
340 /* Set the bitmap DST to the intersection of SRC of successors of
341 block number BB, using the new flow graph structures. */
344 sbitmap_intersection_of_succs (dst
, src
, bb
)
349 basic_block b
= BASIC_BLOCK (bb
);
351 int set_size
= dst
->size
;
353 for ( ; e
!= NULL
; e
= e
->succ_next
)
355 if (e
->dest
== EXIT_BLOCK_PTR
)
357 sbitmap_copy (dst
, src
[e
->dest
->index
]);
364 for ( e
= e
->succ_next
; e
!= NULL
; e
= e
->succ_next
)
369 if (e
->dest
== EXIT_BLOCK_PTR
)
372 p
= src
[e
->dest
->index
]->elms
;
374 for (i
= 0; i
< set_size
; i
++)
380 /* Set the bitmap DST to the intersection of SRC of predecessors of
381 block number BB, using the new flow graph structures. */
384 sbitmap_intersection_of_preds (dst
, src
, bb
)
389 basic_block b
= BASIC_BLOCK (bb
);
391 int set_size
= dst
->size
;
393 for ( ; e
!= NULL
; e
= e
->pred_next
)
395 if (e
->src
== ENTRY_BLOCK_PTR
)
397 sbitmap_copy (dst
, src
[e
->src
->index
]);
404 for ( e
= e
->pred_next
; e
!= NULL
; e
= e
->pred_next
)
409 if (e
->src
== ENTRY_BLOCK_PTR
)
412 p
= src
[e
->src
->index
]->elms
;
414 for (i
= 0; i
< set_size
; i
++)
420 /* Set the bitmap DST to the union of SRC of successors of
421 block number BB, using the new flow graph structures. */
424 sbitmap_union_of_succs (dst
, src
, bb
)
429 basic_block b
= BASIC_BLOCK (bb
);
431 int set_size
= dst
->size
;
433 for ( ; e
!= NULL
; e
= e
->succ_next
)
435 if (e
->dest
== EXIT_BLOCK_PTR
)
437 sbitmap_copy (dst
, src
[e
->dest
->index
]);
444 for ( e
= e
->succ_next
; e
!= NULL
; e
= e
->succ_next
)
449 if (e
->dest
== EXIT_BLOCK_PTR
)
452 p
= src
[e
->dest
->index
]->elms
;
454 for (i
= 0; i
< set_size
; i
++)
460 /* Set the bitmap DST to the union of SRC of predecessors of
461 block number BB, using the new flow graph structures. */
464 sbitmap_union_of_preds (dst
, src
, bb
)
469 basic_block b
= BASIC_BLOCK (bb
);
471 int set_size
= dst
->size
;
473 for ( ; e
!= NULL
; e
= e
->pred_next
)
475 if (e
->src
== ENTRY_BLOCK_PTR
)
477 sbitmap_copy (dst
, src
[e
->src
->index
]);
484 for ( e
= e
->pred_next
; e
!= NULL
; e
= e
->pred_next
)
489 if (e
->src
== ENTRY_BLOCK_PTR
)
492 p
= src
[e
->src
->index
]->elms
;
494 for (i
= 0; i
< set_size
; i
++)
501 dump_sbitmap (file
, bmap
)
506 int set_size
= bmap
->size
;
507 int total_bits
= bmap
->n_bits
;
510 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
512 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
514 if (n
!= 0 && n
% 10 == 0)
516 fprintf (file
, "%d", (bmap
->elms
[i
] & (1L << j
)) != 0);
519 fprintf (file
, "\n");
523 dump_sbitmap_vector (file
, title
, subtitle
, bmaps
, n_maps
)
525 const char *title
, *subtitle
;
531 fprintf (file
, "%s\n", title
);
532 for (bb
= 0; bb
< n_maps
; bb
++)
534 fprintf (file
, "%s %d\n", subtitle
, bb
);
535 dump_sbitmap (file
, bmaps
[bb
]);
537 fprintf (file
, "\n");
This page took 0.065293 seconds and 6 git commands to generate.