1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
32 /* Obstack to allocate bitmap elements from. */
33 static struct obstack bitmap_obstack
;
34 static int bitmap_obstack_init
= FALSE
;
40 #define INLINE __inline__
45 bitmap_element bitmap_zero_bits
; /* An element of all zero bits. */
46 static bitmap_element
*bitmap_free
; /* Freelist of bitmap elements. */
47 static GTY((deletable
)) bitmap_element
*bitmap_ggc_free
;
49 static void bitmap_elem_to_freelist (bitmap
, bitmap_element
*);
50 static void bitmap_element_free (bitmap
, bitmap_element
*);
51 static bitmap_element
*bitmap_element_allocate (bitmap
);
52 static int bitmap_element_zerop (bitmap_element
*);
53 static void bitmap_element_link (bitmap
, bitmap_element
*);
54 static bitmap_element
*bitmap_find_bit (bitmap
, unsigned int);
56 /* Add ELEM to the appropriate freelist. */
58 bitmap_elem_to_freelist (bitmap head
, bitmap_element
*elt
)
60 if (head
->using_obstack
)
62 elt
->next
= bitmap_free
;
67 elt
->next
= bitmap_ggc_free
;
68 bitmap_ggc_free
= elt
;
72 /* Free a bitmap element. Since these are allocated off the
73 bitmap_obstack, "free" actually means "put onto the freelist". */
76 bitmap_element_free (bitmap head
, bitmap_element
*elt
)
78 bitmap_element
*next
= elt
->next
;
79 bitmap_element
*prev
= elt
->prev
;
87 if (head
->first
== elt
)
90 /* Since the first thing we try is to insert before current,
91 make current the next entry in preference to the previous. */
92 if (head
->current
== elt
)
94 head
->current
= next
!= 0 ? next
: prev
;
96 head
->indx
= head
->current
->indx
;
98 bitmap_elem_to_freelist (head
, elt
);
101 /* Allocate a bitmap element. The bits are cleared, but nothing else is. */
103 static INLINE bitmap_element
*
104 bitmap_element_allocate (bitmap head
)
106 bitmap_element
*element
;
108 if (head
->using_obstack
)
110 if (bitmap_free
!= 0)
112 element
= bitmap_free
;
113 bitmap_free
= element
->next
;
117 /* We can't use gcc_obstack_init to initialize the obstack since
118 print-rtl.c now calls bitmap functions, and bitmap is linked
119 into the gen* functions. */
120 if (!bitmap_obstack_init
)
122 bitmap_obstack_init
= TRUE
;
124 #if !defined(__GNUC__) || (__GNUC__ < 2)
125 #define __alignof__(type) 0
128 obstack_specify_allocation (&bitmap_obstack
, OBSTACK_CHUNK_SIZE
,
129 __alignof__ (bitmap_element
),
134 element
= XOBNEW (&bitmap_obstack
, bitmap_element
);
139 if (bitmap_ggc_free
!= NULL
)
141 element
= bitmap_ggc_free
;
142 bitmap_ggc_free
= element
->next
;
145 element
= GGC_NEW (bitmap_element
);
148 memset (element
->bits
, 0, sizeof (element
->bits
));
153 /* Release any memory allocated by bitmaps. */
156 bitmap_release_memory (void)
159 if (bitmap_obstack_init
)
161 bitmap_obstack_init
= FALSE
;
162 obstack_free (&bitmap_obstack
, NULL
);
166 /* Return nonzero if all bits in an element are zero. */
169 bitmap_element_zerop (bitmap_element
*element
)
171 #if BITMAP_ELEMENT_WORDS == 2
172 return (element
->bits
[0] | element
->bits
[1]) == 0;
176 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
177 if (element
->bits
[i
] != 0)
184 /* Link the bitmap element into the current bitmap linked list. */
187 bitmap_element_link (bitmap head
, bitmap_element
*element
)
189 unsigned int indx
= element
->indx
;
192 /* If this is the first and only element, set it in. */
193 if (head
->first
== 0)
195 element
->next
= element
->prev
= 0;
196 head
->first
= element
;
199 /* If this index is less than that of the current element, it goes someplace
200 before the current element. */
201 else if (indx
< head
->indx
)
203 for (ptr
= head
->current
;
204 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
209 ptr
->prev
->next
= element
;
211 head
->first
= element
;
213 element
->prev
= ptr
->prev
;
218 /* Otherwise, it must go someplace after the current element. */
221 for (ptr
= head
->current
;
222 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
227 ptr
->next
->prev
= element
;
229 element
->next
= ptr
->next
;
234 /* Set up so this is the first element searched. */
235 head
->current
= element
;
239 /* Clear a bitmap by freeing the linked list. */
242 bitmap_clear (bitmap head
)
244 bitmap_element
*element
, *next
;
246 for (element
= head
->first
; element
!= 0; element
= next
)
248 next
= element
->next
;
249 bitmap_elem_to_freelist (head
, element
);
252 head
->first
= head
->current
= 0;
255 /* Copy a bitmap to another bitmap. */
258 bitmap_copy (bitmap to
, bitmap from
)
260 bitmap_element
*from_ptr
, *to_ptr
= 0;
261 #if BITMAP_ELEMENT_WORDS != 2
267 /* Copy elements in forward direction one at a time. */
268 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
270 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
272 to_elt
->indx
= from_ptr
->indx
;
274 #if BITMAP_ELEMENT_WORDS == 2
275 to_elt
->bits
[0] = from_ptr
->bits
[0];
276 to_elt
->bits
[1] = from_ptr
->bits
[1];
278 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
279 to_elt
->bits
[i
] = from_ptr
->bits
[i
];
282 /* Here we have a special case of bitmap_element_link, for the case
283 where we know the links are being entered in sequence. */
286 to
->first
= to
->current
= to_elt
;
287 to
->indx
= from_ptr
->indx
;
288 to_elt
->next
= to_elt
->prev
= 0;
292 to_elt
->prev
= to_ptr
;
294 to_ptr
->next
= to_elt
;
301 /* Find a bitmap element that would hold a bitmap's bit.
302 Update the `current' field even if we can't find an element that
303 would hold the bitmap's bit to make eventual allocation
306 static INLINE bitmap_element
*
307 bitmap_find_bit (bitmap head
, unsigned int bit
)
309 bitmap_element
*element
;
310 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
312 if (head
->current
== 0
313 || head
->indx
== indx
)
314 return head
->current
;
316 if (head
->indx
> indx
)
317 for (element
= head
->current
;
318 element
->prev
!= 0 && element
->indx
> indx
;
319 element
= element
->prev
)
323 for (element
= head
->current
;
324 element
->next
!= 0 && element
->indx
< indx
;
325 element
= element
->next
)
328 /* `element' is the nearest to the one we want. If it's not the one we
329 want, the one we want doesn't exist. */
330 head
->current
= element
;
331 head
->indx
= element
->indx
;
332 if (element
!= 0 && element
->indx
!= indx
)
338 /* Clear a single bit in a bitmap. */
341 bitmap_clear_bit (bitmap head
, int bit
)
343 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
347 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
348 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
349 ptr
->bits
[word_num
] &= ~ (((BITMAP_WORD
) 1) << bit_num
);
351 /* If we cleared the entire word, free up the element. */
352 if (bitmap_element_zerop (ptr
))
353 bitmap_element_free (head
, ptr
);
357 /* Set a single bit in a bitmap. */
360 bitmap_set_bit (bitmap head
, int bit
)
362 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
363 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
364 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
365 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
369 ptr
= bitmap_element_allocate (head
);
370 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
371 ptr
->bits
[word_num
] = bit_val
;
372 bitmap_element_link (head
, ptr
);
375 ptr
->bits
[word_num
] |= bit_val
;
378 /* Return whether a bit is set within a bitmap. */
381 bitmap_bit_p (bitmap head
, int bit
)
387 ptr
= bitmap_find_bit (head
, bit
);
391 bit_num
= bit
% BITMAP_WORD_BITS
;
392 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
394 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
397 /* Return the bit number of the first set bit in the bitmap, or -1
398 if the bitmap is empty. */
401 bitmap_first_set_bit (bitmap a
)
403 bitmap_element
*ptr
= a
->first
;
405 unsigned word_num
, bit_num
;
410 #if BITMAP_ELEMENT_WORDS == 2
411 word_num
= 0, word
= ptr
->bits
[0];
413 word_num
= 1, word
= ptr
->bits
[1];
415 for (word_num
= 0; word_num
< BITMAP_ELEMENT_WORDS
; ++word_num
)
416 if ((word
= ptr
->bits
[word_num
]) != 0)
422 /* Binary search for the first set bit. */
423 /* ??? It'd be nice to know if ffs or ffsl was available. */
428 #if nBITMAP_WORD_BITS > 64
429 #error "Fill out the table."
431 #if nBITMAP_WORD_BITS > 32
432 if ((word
& 0xffffffff) == 0)
433 word
>>= 32, bit_num
+= 32;
435 if ((word
& 0xffff) == 0)
436 word
>>= 16, bit_num
+= 16;
437 if ((word
& 0xff) == 0)
438 word
>>= 8, bit_num
+= 8;
446 return (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
447 + word_num
* BITMAP_WORD_BITS
451 /* Return the bit number of the last set bit in the bitmap, or -1
452 if the bitmap is empty. */
455 bitmap_last_set_bit (bitmap a
)
457 bitmap_element
*ptr
= a
->first
;
459 unsigned word_num
, bit_num
;
464 while (ptr
->next
!= NULL
)
467 #if BITMAP_ELEMENT_WORDS == 2
468 word_num
= 1, word
= ptr
->bits
[1];
470 word_num
= 0, word
= ptr
->bits
[0];
472 for (word_num
= BITMAP_ELEMENT_WORDS
; word_num
-- > 0; )
473 if ((word
= ptr
->bits
[word_num
]) != 0)
479 /* Binary search for the last set bit. */
482 #if nBITMAP_WORD_BITS > 64
483 #error "Fill out the table."
485 #if nBITMAP_WORD_BITS > 32
486 if (word
& ~(BITMAP_WORD
)0xffffffff)
487 word
>>= 32, bit_num
+= 32;
489 if (word
& 0xffff0000)
490 word
>>= 16, bit_num
+= 16;
492 word
>>= 8, bit_num
+= 8;
494 word
>>= 4, bit_num
+= 4;
496 word
>>= 2, bit_num
+= 2;
500 return (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
501 + word_num
* BITMAP_WORD_BITS
505 /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
506 a specific bit manipulation. Return true if TO changes. */
509 bitmap_operation (bitmap to
, bitmap from1
, bitmap from2
,
510 enum bitmap_bits operation
)
512 #define HIGHEST_INDEX (unsigned int) ~0
514 bitmap_element
*from1_ptr
= from1
->first
;
515 bitmap_element
*from2_ptr
= from2
->first
;
516 unsigned int indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
517 unsigned int indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
518 bitmap_element
*to_ptr
= to
->first
;
519 bitmap_element
*from1_tmp
;
520 bitmap_element
*from2_tmp
;
521 bitmap_element
*to_tmp
;
525 #if BITMAP_ELEMENT_WORDS == 2
528 BITMAP_WORD t0, t1, f10, f11, f20, f21; \
529 f10 = from1_tmp->bits[0]; \
530 f20 = from2_tmp->bits[0]; \
532 changed |= (t0 != to_tmp->bits[0]); \
533 f11 = from1_tmp->bits[1]; \
534 f21 = from2_tmp->bits[1]; \
536 changed |= (t1 != to_tmp->bits[1]); \
537 to_tmp->bits[0] = t0; \
538 to_tmp->bits[1] = t1; \
543 BITMAP_WORD t, f1, f2; \
545 for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i) \
547 f1 = from1_tmp->bits[i]; \
548 f2 = from2_tmp->bits[i]; \
550 changed |= (t != to_tmp->bits[i]); \
551 to_tmp->bits[i] = t; \
556 to
->first
= to
->current
= 0;
558 while (from1_ptr
!= 0 || from2_ptr
!= 0)
560 /* Figure out whether we need to substitute zero elements for
565 from1_tmp
= from1_ptr
;
566 from2_tmp
= from2_ptr
;
567 from1_ptr
= from1_ptr
->next
;
568 indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
569 from2_ptr
= from2_ptr
->next
;
570 indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
572 else if (indx1
< indx2
)
575 from1_tmp
= from1_ptr
;
576 from2_tmp
= &bitmap_zero_bits
;
577 from1_ptr
= from1_ptr
->next
;
578 indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
583 from1_tmp
= &bitmap_zero_bits
;
584 from2_tmp
= from2_ptr
;
585 from2_ptr
= from2_ptr
->next
;
586 indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
589 /* Find the appropriate element from TO. Begin by discarding
590 elements that we've skipped. */
591 while (to_ptr
&& to_ptr
->indx
< indx
)
595 to_ptr
= to_ptr
->next
;
596 bitmap_elem_to_freelist (to
, to_tmp
);
598 if (to_ptr
&& to_ptr
->indx
== indx
)
601 to_ptr
= to_ptr
->next
;
604 to_tmp
= bitmap_element_allocate (to
);
606 /* Do the operation, and if any bits are set, link it into the
617 case BITMAP_AND_COMPL
:
624 case BITMAP_IOR_COMPL
:
632 if (! bitmap_element_zerop (to_tmp
))
635 bitmap_element_link (to
, to_tmp
);
639 bitmap_elem_to_freelist (to
, to_tmp
);
643 /* If we have elements of TO left over, free the lot. */
647 for (to_tmp
= to_ptr
; to_tmp
->next
; to_tmp
= to_tmp
->next
)
649 if (to
->using_obstack
)
651 to_tmp
->next
= bitmap_free
;
652 bitmap_free
= to_ptr
;
656 to_tmp
->next
= bitmap_ggc_free
;
657 bitmap_ggc_free
= to_ptr
;
666 /* Return true if two bitmaps are identical. */
669 bitmap_equal_p (bitmap a
, bitmap b
)
674 memset (&c
, 0, sizeof (c
));
675 ret
= ! bitmap_operation (&c
, a
, b
, BITMAP_XOR
);
681 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
685 bitmap_ior_and_compl (bitmap to
, bitmap from1
, bitmap from2
)
689 tmp
.first
= tmp
.current
= 0;
690 tmp
.using_obstack
= 0;
692 bitmap_operation (&tmp
, from1
, from2
, BITMAP_AND_COMPL
);
693 bitmap_operation (to
, to
, &tmp
, BITMAP_IOR
);
698 bitmap_union_of_diff (bitmap dst
, bitmap a
, bitmap b
, bitmap c
)
703 tmp
.first
= tmp
.current
= 0;
704 tmp
.using_obstack
= 0;
706 bitmap_operation (&tmp
, b
, c
, BITMAP_AND_COMPL
);
707 changed
= bitmap_operation (dst
, &tmp
, a
, BITMAP_IOR
);
713 /* Initialize a bitmap header. */
716 bitmap_initialize (bitmap head
, int using_obstack
)
718 if (head
== NULL
&& ! using_obstack
)
719 head
= GGC_NEW (struct bitmap_head_def
);
721 head
->first
= head
->current
= 0;
722 head
->using_obstack
= using_obstack
;
727 /* Debugging function to print out the contents of a bitmap. */
730 debug_bitmap_file (FILE *file
, bitmap head
)
734 fprintf (file
, "\nfirst = " HOST_PTR_PRINTF
735 " current = " HOST_PTR_PRINTF
" indx = %u\n",
736 (void *) head
->first
, (void *) head
->current
, head
->indx
);
738 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
740 unsigned int i
, j
, col
= 26;
742 fprintf (file
, "\t" HOST_PTR_PRINTF
" next = " HOST_PTR_PRINTF
743 " prev = " HOST_PTR_PRINTF
" indx = %u\n\t\tbits = {",
744 (void*) ptr
, (void*) ptr
->next
, (void*) ptr
->prev
, ptr
->indx
);
746 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
747 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
748 if ((ptr
->bits
[i
] >> j
) & 1)
752 fprintf (file
, "\n\t\t\t");
756 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
757 + i
* BITMAP_WORD_BITS
+ j
));
761 fprintf (file
, " }\n");
765 /* Function to be called from the debugger to print the contents
769 debug_bitmap (bitmap head
)
771 debug_bitmap_file (stdout
, head
);
774 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
775 it does not print anything but the bits. */
778 bitmap_print (FILE *file
, bitmap head
, const char *prefix
, const char *suffix
)
780 const char *comma
= "";
784 fputs (prefix
, file
);
785 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
, bi
)
787 fprintf (file
, "%s%d", comma
, i
);
790 fputs (suffix
, file
);
793 #include "gt-bitmap.h"