]>
gcc.gnu.org Git - gcc.git/blob - gcc/sbitmap.c
2 Copyright (C) 1999, 2000 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
)
35 unsigned int bytes
, size
, amt
;
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
)
53 unsigned int n_vecs
, n_elms
;
55 unsigned 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
; i
< n_vecs
; i
++, offset
+= elm_bytes
)
81 sbitmap b
= (sbitmap
) ((char *) bitmap_vector
+ offset
);
92 /* Copy sbitmap SRC to DST. */
95 sbitmap_copy (dst
, src
)
98 bcopy ((PTR
) src
->elms
, (PTR
) dst
->elms
,
99 sizeof (SBITMAP_ELT_TYPE
) * dst
->size
);
102 /* Zero all elements in a bitmap. */
108 bzero ((PTR
) bmap
->elms
, bmap
->bytes
);
111 /* Set all elements in a bitmap to ones. */
117 unsigned int last_bit
;
119 memset ((PTR
) bmap
->elms
, -1, bmap
->bytes
);
121 last_bit
= bmap
->n_bits
% SBITMAP_ELT_BITS
;
123 bmap
->elms
[bmap
->size
- 1]
124 = (SBITMAP_ELT_TYPE
)-1 >> (SBITMAP_ELT_BITS
- last_bit
);
127 /* Zero a vector of N_VECS bitmaps. */
130 sbitmap_vector_zero (bmap
, n_vecs
)
136 for (i
= 0; i
< n_vecs
; i
++)
137 sbitmap_zero (bmap
[i
]);
140 /* Set a vector of N_VECS bitmaps to ones. */
143 sbitmap_vector_ones (bmap
, n_vecs
)
149 for (i
= 0; i
< n_vecs
; i
++)
150 sbitmap_ones (bmap
[i
]);
153 /* Set DST to be A union (B - C).
155 Return non-zero if any change is made. */
158 sbitmap_union_of_diff (dst
, a
, b
, c
)
159 sbitmap dst
, a
, b
, c
;
162 sbitmap_ptr dstp
, ap
, bp
, cp
;
165 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, cp
= c
->elms
, i
= 0;
166 i
< dst
->size
; i
++, dstp
++)
168 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & ~*cp
++);
180 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */
183 sbitmap_not (dst
, src
)
187 sbitmap_ptr dstp
, srcp
;
189 for (dstp
= dst
->elms
, srcp
= src
->elms
, i
= 0; i
< dst
->size
; i
++)
190 *dstp
++ = ~(*srcp
++);
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). */
197 sbitmap_difference (dst
, a
, b
)
201 sbitmap_ptr dstp
, ap
, bp
;
203 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< dst
->size
; i
++)
204 *dstp
++ = *ap
++ & (~*bp
++);
207 /* Set DST to be (A and B).
208 Return non-zero if any change is made. */
211 sbitmap_a_and_b (dst
, a
, b
)
215 sbitmap_ptr dstp
, ap
, bp
;
218 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< dst
->size
;
221 SBITMAP_ELT_TYPE tmp
= *ap
++ & *bp
++;
233 /* Set DST to be (A or B)).
234 Return non-zero if any change is made. */
237 sbitmap_a_or_b (dst
, a
, b
)
241 sbitmap_ptr dstp
, ap
, bp
;
244 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< dst
->size
;
247 SBITMAP_ELT_TYPE tmp
= *ap
++ | *bp
++;
259 /* Return non-zero if A is a subset of B. */
262 sbitmap_a_subset_b_p (a
, b
)
268 for (ap
= a
->elms
, bp
= b
->elms
, i
= 0; i
< a
->size
; i
++, ap
++, bp
++)
269 if ((*ap
| *bp
) != *bp
)
275 /* Set DST to be (A or (B and C)).
276 Return non-zero if any change is made. */
279 sbitmap_a_or_b_and_c (dst
, a
, b
, c
)
280 sbitmap dst
, a
, b
, c
;
283 sbitmap_ptr dstp
, ap
, bp
, cp
;
286 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, cp
= c
->elms
, i
= 0;
287 i
< dst
->size
; i
++, dstp
++)
289 SBITMAP_ELT_TYPE tmp
= *ap
++ | (*bp
++ & *cp
++);
301 /* Set DST to be (A and (B or C)).
302 Return non-zero if any change is made. */
305 sbitmap_a_and_b_or_c (dst
, a
, b
, c
)
306 sbitmap dst
, a
, b
, c
;
309 sbitmap_ptr dstp
, ap
, bp
, cp
;
312 for (dstp
= dst
->elms
, ap
= a
->elms
, bp
= b
->elms
, cp
= c
->elms
, i
= 0;
313 i
< dst
->size
; i
++, dstp
++)
315 SBITMAP_ELT_TYPE tmp
= *ap
++ & (*bp
++ | *cp
++);
327 /* Set the bitmap DST to the intersection of SRC of successors of
328 block number BB, using the new flow graph structures. */
331 sbitmap_intersection_of_succs (dst
, src
, bb
)
336 basic_block b
= BASIC_BLOCK (bb
);
337 unsigned int set_size
= dst
->size
;
340 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
342 if (e
->dest
== EXIT_BLOCK_PTR
)
345 sbitmap_copy (dst
, src
[e
->dest
->index
]);
352 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
357 if (e
->dest
== EXIT_BLOCK_PTR
)
360 p
= src
[e
->dest
->index
]->elms
;
362 for (i
= 0; i
< set_size
; i
++)
367 /* Set the bitmap DST to the intersection of SRC of predecessors of
368 block number BB, using the new flow graph structures. */
371 sbitmap_intersection_of_preds (dst
, src
, bb
)
376 basic_block b
= BASIC_BLOCK (bb
);
377 unsigned int set_size
= dst
->size
;
380 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
382 if (e
->src
== ENTRY_BLOCK_PTR
)
385 sbitmap_copy (dst
, src
[e
->src
->index
]);
392 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
397 if (e
->src
== ENTRY_BLOCK_PTR
)
400 p
= src
[e
->src
->index
]->elms
;
402 for (i
= 0; i
< set_size
; i
++)
407 /* Set the bitmap DST to the union of SRC of successors of
408 block number BB, using the new flow graph structures. */
411 sbitmap_union_of_succs (dst
, src
, bb
)
416 basic_block b
= BASIC_BLOCK (bb
);
417 unsigned int set_size
= dst
->size
;
420 for (e
= b
->succ
; e
!= 0; e
= e
->succ_next
)
422 if (e
->dest
== EXIT_BLOCK_PTR
)
425 sbitmap_copy (dst
, src
[e
->dest
->index
]);
432 for (e
= e
->succ_next
; e
!= 0; e
= e
->succ_next
)
437 if (e
->dest
== EXIT_BLOCK_PTR
)
440 p
= src
[e
->dest
->index
]->elms
;
442 for (i
= 0; i
< set_size
; i
++)
447 /* Set the bitmap DST to the union of SRC of predecessors of
448 block number BB, using the new flow graph structures. */
451 sbitmap_union_of_preds (dst
, src
, bb
)
456 basic_block b
= BASIC_BLOCK (bb
);
457 unsigned int set_size
= dst
->size
;
460 for (e
= b
->pred
; e
!= 0; e
= e
->pred_next
)
462 if (e
->src
== ENTRY_BLOCK_PTR
)
465 sbitmap_copy (dst
, src
[e
->src
->index
]);
472 for (e
= e
->pred_next
; e
!= 0; e
= e
->pred_next
)
477 if (e
->src
== ENTRY_BLOCK_PTR
)
480 p
= src
[e
->src
->index
]->elms
;
482 for (i
= 0; i
< set_size
; i
++)
487 /* Return number of first bit set in the bitmap, -1 if none. */
490 sbitmap_first_set_bit (bmap
)
495 EXECUTE_IF_SET_IN_SBITMAP (bmap
, 0, n
, { return n
; });
499 /* Return number of last bit set in the bitmap, -1 if none. */
502 sbitmap_last_set_bit (bmap
)
506 SBITMAP_ELT_TYPE
*ptr
= bmap
->elms
;
508 for (i
= bmap
->size
- 1; i
>= 0; i
--)
510 SBITMAP_ELT_TYPE word
= ptr
[i
];
514 unsigned int index
= (i
+ 1) * SBITMAP_ELT_BITS
- 1;
515 SBITMAP_ELT_TYPE mask
516 = (SBITMAP_ELT_TYPE
) 1 << (SBITMAP_ELT_BITS
- 1);
520 if ((word
& mask
) != 0)
533 dump_sbitmap (file
, bmap
)
537 unsigned int i
, n
, j
;
538 unsigned int set_size
= bmap
->size
;
539 unsigned int total_bits
= bmap
->n_bits
;
542 for (i
= n
= 0; i
< set_size
&& n
< total_bits
; i
++)
543 for (j
= 0; j
< SBITMAP_ELT_BITS
&& n
< total_bits
; j
++, n
++)
545 if (n
!= 0 && n
% 10 == 0)
549 (bmap
->elms
[i
] & ((SBITMAP_ELT_TYPE
) 1 << j
)) != 0);
552 fprintf (file
, "\n");
561 fprintf (stderr
, "n_bits = %d, set = {", bmap
->n_bits
);
563 for (pos
= 30, i
= 0; i
< bmap
->n_bits
; i
++)
564 if (TEST_BIT (bmap
, i
))
568 fprintf (stderr
, "\n");
572 fprintf (stderr
, "%d ", i
);
573 pos
+= 1 + (i
>= 10) + (i
>= 100);
576 fprintf (stderr
, "}\n");
580 dump_sbitmap_vector (file
, title
, subtitle
, bmaps
, n_maps
)
582 const char *title
, *subtitle
;
588 fprintf (file
, "%s\n", title
);
589 for (bb
= 0; bb
< n_maps
; bb
++)
591 fprintf (file
, "%s %d\n", subtitle
, bb
);
592 dump_sbitmap (file
, bmaps
[bb
]);
595 fprintf (file
, "\n");
This page took 0.063783 seconds and 5 git commands to generate.