1 /* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003
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
= (bitmap_element
*) obstack_alloc (&bitmap_obstack
,
135 sizeof (bitmap_element
));
140 if (bitmap_ggc_free
!= NULL
)
142 element
= bitmap_ggc_free
;
143 bitmap_ggc_free
= element
->next
;
146 element
= ggc_alloc (sizeof (bitmap_element
));
149 memset (element
->bits
, 0, sizeof (element
->bits
));
154 /* Release any memory allocated by bitmaps. */
157 bitmap_release_memory (void)
160 if (bitmap_obstack_init
)
162 bitmap_obstack_init
= FALSE
;
163 obstack_free (&bitmap_obstack
, NULL
);
167 /* Return nonzero if all bits in an element are zero. */
170 bitmap_element_zerop (bitmap_element
*element
)
172 #if BITMAP_ELEMENT_WORDS == 2
173 return (element
->bits
[0] | element
->bits
[1]) == 0;
177 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
178 if (element
->bits
[i
] != 0)
185 /* Link the bitmap element into the current bitmap linked list. */
188 bitmap_element_link (bitmap head
, bitmap_element
*element
)
190 unsigned int indx
= element
->indx
;
193 /* If this is the first and only element, set it in. */
194 if (head
->first
== 0)
196 element
->next
= element
->prev
= 0;
197 head
->first
= element
;
200 /* If this index is less than that of the current element, it goes someplace
201 before the current element. */
202 else if (indx
< head
->indx
)
204 for (ptr
= head
->current
;
205 ptr
->prev
!= 0 && ptr
->prev
->indx
> indx
;
210 ptr
->prev
->next
= element
;
212 head
->first
= element
;
214 element
->prev
= ptr
->prev
;
219 /* Otherwise, it must go someplace after the current element. */
222 for (ptr
= head
->current
;
223 ptr
->next
!= 0 && ptr
->next
->indx
< indx
;
228 ptr
->next
->prev
= element
;
230 element
->next
= ptr
->next
;
235 /* Set up so this is the first element searched. */
236 head
->current
= element
;
240 /* Clear a bitmap by freeing the linked list. */
243 bitmap_clear (bitmap head
)
245 bitmap_element
*element
, *next
;
247 for (element
= head
->first
; element
!= 0; element
= next
)
249 next
= element
->next
;
250 bitmap_elem_to_freelist (head
, element
);
253 head
->first
= head
->current
= 0;
256 /* Copy a bitmap to another bitmap. */
259 bitmap_copy (bitmap to
, bitmap from
)
261 bitmap_element
*from_ptr
, *to_ptr
= 0;
262 #if BITMAP_ELEMENT_WORDS != 2
268 /* Copy elements in forward direction one at a time. */
269 for (from_ptr
= from
->first
; from_ptr
; from_ptr
= from_ptr
->next
)
271 bitmap_element
*to_elt
= bitmap_element_allocate (to
);
273 to_elt
->indx
= from_ptr
->indx
;
275 #if BITMAP_ELEMENT_WORDS == 2
276 to_elt
->bits
[0] = from_ptr
->bits
[0];
277 to_elt
->bits
[1] = from_ptr
->bits
[1];
279 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
280 to_elt
->bits
[i
] = from_ptr
->bits
[i
];
283 /* Here we have a special case of bitmap_element_link, for the case
284 where we know the links are being entered in sequence. */
287 to
->first
= to
->current
= to_elt
;
288 to
->indx
= from_ptr
->indx
;
289 to_elt
->next
= to_elt
->prev
= 0;
293 to_elt
->prev
= to_ptr
;
295 to_ptr
->next
= to_elt
;
302 /* Find a bitmap element that would hold a bitmap's bit.
303 Update the `current' field even if we can't find an element that
304 would hold the bitmap's bit to make eventual allocation
307 static INLINE bitmap_element
*
308 bitmap_find_bit (bitmap head
, unsigned int bit
)
310 bitmap_element
*element
;
311 unsigned int indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
313 if (head
->current
== 0
314 || head
->indx
== indx
)
315 return head
->current
;
317 if (head
->indx
> indx
)
318 for (element
= head
->current
;
319 element
->prev
!= 0 && element
->indx
> indx
;
320 element
= element
->prev
)
324 for (element
= head
->current
;
325 element
->next
!= 0 && element
->indx
< indx
;
326 element
= element
->next
)
329 /* `element' is the nearest to the one we want. If it's not the one we
330 want, the one we want doesn't exist. */
331 head
->current
= element
;
332 head
->indx
= element
->indx
;
333 if (element
!= 0 && element
->indx
!= indx
)
339 /* Clear a single bit in a bitmap. */
342 bitmap_clear_bit (bitmap head
, int bit
)
344 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
348 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
349 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
350 ptr
->bits
[word_num
] &= ~ (((BITMAP_WORD
) 1) << bit_num
);
352 /* If we cleared the entire word, free up the element */
353 if (bitmap_element_zerop (ptr
))
354 bitmap_element_free (head
, ptr
);
358 /* Set a single bit in a bitmap. */
361 bitmap_set_bit (bitmap head
, int bit
)
363 bitmap_element
*ptr
= bitmap_find_bit (head
, bit
);
364 unsigned word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
365 unsigned bit_num
= bit
% BITMAP_WORD_BITS
;
366 BITMAP_WORD bit_val
= ((BITMAP_WORD
) 1) << bit_num
;
370 ptr
= bitmap_element_allocate (head
);
371 ptr
->indx
= bit
/ BITMAP_ELEMENT_ALL_BITS
;
372 ptr
->bits
[word_num
] = bit_val
;
373 bitmap_element_link (head
, ptr
);
376 ptr
->bits
[word_num
] |= bit_val
;
379 /* Return whether a bit is set within a bitmap. */
382 bitmap_bit_p (bitmap head
, int bit
)
388 ptr
= bitmap_find_bit (head
, bit
);
392 bit_num
= bit
% BITMAP_WORD_BITS
;
393 word_num
= bit
/ BITMAP_WORD_BITS
% BITMAP_ELEMENT_WORDS
;
395 return (ptr
->bits
[word_num
] >> bit_num
) & 1;
398 /* Return the bit number of the first set bit in the bitmap, or -1
399 if the bitmap is empty. */
402 bitmap_first_set_bit (bitmap a
)
404 bitmap_element
*ptr
= a
->first
;
406 unsigned word_num
, bit_num
;
411 #if BITMAP_ELEMENT_WORDS == 2
412 word_num
= 0, word
= ptr
->bits
[0];
414 word_num
= 1, word
= ptr
->bits
[1];
416 for (word_num
= 0; word_num
< BITMAP_ELEMENT_WORDS
; ++word_num
)
417 if ((word
= ptr
->bits
[word_num
]) != 0)
421 /* Binary search for the first set bit. */
422 /* ??? It'd be nice to know if ffs or ffsl was available. */
427 #if nBITMAP_WORD_BITS > 64
428 #error "Fill out the table."
430 #if nBITMAP_WORD_BITS > 32
431 if ((word
& 0xffffffff) == 0)
432 word
>>= 32, bit_num
+= 32;
434 if ((word
& 0xffff) == 0)
435 word
>>= 16, bit_num
+= 16;
436 if ((word
& 0xff) == 0)
437 word
>>= 8, bit_num
+= 8;
445 return (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
446 + word_num
* BITMAP_WORD_BITS
450 /* Return the bit number of the last set bit in the bitmap, or -1
451 if the bitmap is empty. */
454 bitmap_last_set_bit (bitmap a
)
456 bitmap_element
*ptr
= a
->first
;
458 unsigned word_num
, bit_num
;
463 while (ptr
->next
!= NULL
)
466 #if BITMAP_ELEMENT_WORDS == 2
467 word_num
= 1, word
= ptr
->bits
[1];
469 word_num
= 0, word
= ptr
->bits
[0];
471 for (word_num
= BITMAP_ELEMENT_WORDS
; word_num
-- > 0; )
472 if ((word
= ptr
->bits
[word_num
]) != 0)
476 /* Binary search for the last set bit. */
479 #if nBITMAP_WORD_BITS > 64
480 #error "Fill out the table."
482 #if nBITMAP_WORD_BITS > 32
483 if (word
& ~(BITMAP_WORD
)0xffffffff)
484 word
>>= 32, bit_num
+= 32;
486 if (word
& 0xffff0000)
487 word
>>= 16, bit_num
+= 16;
489 word
>>= 8, bit_num
+= 8;
491 word
>>= 4, bit_num
+= 4;
493 word
>>= 2, bit_num
+= 2;
497 return (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
498 + word_num
* BITMAP_WORD_BITS
502 /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
503 a specific bit manipulation. Return true if TO changes. */
506 bitmap_operation (bitmap to
, bitmap from1
, bitmap from2
,
507 enum bitmap_bits operation
)
509 #define HIGHEST_INDEX (unsigned int) ~0
511 bitmap_element
*from1_ptr
= from1
->first
;
512 bitmap_element
*from2_ptr
= from2
->first
;
513 unsigned int indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
514 unsigned int indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
515 bitmap_element
*to_ptr
= to
->first
;
516 bitmap_element
*from1_tmp
;
517 bitmap_element
*from2_tmp
;
518 bitmap_element
*to_tmp
;
522 #if BITMAP_ELEMENT_WORDS == 2
525 BITMAP_WORD t0, t1, f10, f11, f20, f21; \
526 f10 = from1_tmp->bits[0]; \
527 f20 = from2_tmp->bits[0]; \
529 changed |= (t0 != to_tmp->bits[0]); \
530 f11 = from1_tmp->bits[1]; \
531 f21 = from2_tmp->bits[1]; \
533 changed |= (t1 != to_tmp->bits[1]); \
534 to_tmp->bits[0] = t0; \
535 to_tmp->bits[1] = t1; \
540 BITMAP_WORD t, f1, f2; \
542 for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i) \
544 f1 = from1_tmp->bits[i]; \
545 f2 = from2_tmp->bits[i]; \
547 changed |= (t != to_tmp->bits[i]); \
548 to_tmp->bits[i] = t; \
553 to
->first
= to
->current
= 0;
555 while (from1_ptr
!= 0 || from2_ptr
!= 0)
557 /* Figure out whether we need to substitute zero elements for
562 from1_tmp
= from1_ptr
;
563 from2_tmp
= from2_ptr
;
564 from1_ptr
= from1_ptr
->next
;
565 indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
566 from2_ptr
= from2_ptr
->next
;
567 indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
569 else if (indx1
< indx2
)
572 from1_tmp
= from1_ptr
;
573 from2_tmp
= &bitmap_zero_bits
;
574 from1_ptr
= from1_ptr
->next
;
575 indx1
= (from1_ptr
) ? from1_ptr
->indx
: HIGHEST_INDEX
;
580 from1_tmp
= &bitmap_zero_bits
;
581 from2_tmp
= from2_ptr
;
582 from2_ptr
= from2_ptr
->next
;
583 indx2
= (from2_ptr
) ? from2_ptr
->indx
: HIGHEST_INDEX
;
586 /* Find the appropriate element from TO. Begin by discarding
587 elements that we've skipped. */
588 while (to_ptr
&& to_ptr
->indx
< indx
)
592 to_ptr
= to_ptr
->next
;
593 bitmap_elem_to_freelist (to
, to_tmp
);
595 if (to_ptr
&& to_ptr
->indx
== indx
)
598 to_ptr
= to_ptr
->next
;
601 to_tmp
= bitmap_element_allocate (to
);
603 /* Do the operation, and if any bits are set, link it into the
614 case BITMAP_AND_COMPL
:
621 case BITMAP_IOR_COMPL
:
629 if (! bitmap_element_zerop (to_tmp
))
632 bitmap_element_link (to
, to_tmp
);
636 bitmap_elem_to_freelist (to
, to_tmp
);
640 /* If we have elements of TO left over, free the lot. */
644 for (to_tmp
= to_ptr
; to_tmp
->next
; to_tmp
= to_tmp
->next
)
646 if (to
->using_obstack
)
648 to_tmp
->next
= bitmap_free
;
649 bitmap_free
= to_ptr
;
653 to_tmp
->next
= bitmap_ggc_free
;
654 bitmap_ggc_free
= to_ptr
;
663 /* Return true if two bitmaps are identical. */
666 bitmap_equal_p (bitmap a
, bitmap b
)
671 memset (&c
, 0, sizeof (c
));
672 ret
= ! bitmap_operation (&c
, a
, b
, BITMAP_XOR
);
678 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
682 bitmap_ior_and_compl (bitmap to
, bitmap from1
, bitmap from2
)
686 tmp
.first
= tmp
.current
= 0;
687 tmp
.using_obstack
= 0;
689 bitmap_operation (&tmp
, from1
, from2
, BITMAP_AND_COMPL
);
690 bitmap_operation (to
, to
, &tmp
, BITMAP_IOR
);
695 bitmap_union_of_diff (bitmap dst
, bitmap a
, bitmap b
, bitmap c
)
700 tmp
.first
= tmp
.current
= 0;
701 tmp
.using_obstack
= 0;
703 bitmap_operation (&tmp
, b
, c
, BITMAP_AND_COMPL
);
704 changed
= bitmap_operation (dst
, &tmp
, a
, BITMAP_IOR
);
710 /* Initialize a bitmap header. */
713 bitmap_initialize (bitmap head
, int using_obstack
)
715 if (head
== NULL
&& ! using_obstack
)
716 head
= ggc_alloc (sizeof (*head
));
718 head
->first
= head
->current
= 0;
719 head
->using_obstack
= using_obstack
;
724 /* Debugging function to print out the contents of a bitmap. */
727 debug_bitmap_file (FILE *file
, bitmap head
)
731 fprintf (file
, "\nfirst = ");
732 fprintf (file
, HOST_PTR_PRINTF
, (void *) head
->first
);
733 fprintf (file
, " current = ");
734 fprintf (file
, HOST_PTR_PRINTF
, (void *) head
->current
);
735 fprintf (file
, " indx = %u\n", head
->indx
);
737 for (ptr
= head
->first
; ptr
; ptr
= ptr
->next
)
739 unsigned int i
, j
, col
= 26;
741 fprintf (file
, "\t");
742 fprintf (file
, HOST_PTR_PRINTF
, (void *) ptr
);
743 fprintf (file
, " next = ");
744 fprintf (file
, HOST_PTR_PRINTF
, (void *) ptr
->next
);
745 fprintf (file
, " prev = ");
746 fprintf (file
, HOST_PTR_PRINTF
, (void *) ptr
->prev
);
747 fprintf (file
, " indx = %u\n\t\tbits = {", ptr
->indx
);
749 for (i
= 0; i
< BITMAP_ELEMENT_WORDS
; i
++)
750 for (j
= 0; j
< BITMAP_WORD_BITS
; j
++)
751 if ((ptr
->bits
[i
] >> j
) & 1)
755 fprintf (file
, "\n\t\t\t");
759 fprintf (file
, " %u", (ptr
->indx
* BITMAP_ELEMENT_ALL_BITS
760 + i
* BITMAP_WORD_BITS
+ j
));
764 fprintf (file
, " }\n");
768 /* Function to be called from the debugger to print the contents
772 debug_bitmap (bitmap head
)
774 debug_bitmap_file (stdout
, head
);
777 /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file,
778 it does not print anything but the bits. */
781 bitmap_print (FILE *file
, bitmap head
, const char *prefix
, const char *suffix
)
783 const char *comma
= "";
786 fputs (prefix
, file
);
787 EXECUTE_IF_SET_IN_BITMAP (head
, 0, i
,
789 fprintf (file
, "%s%d", comma
, i
);
792 fputs (suffix
, file
);
795 #include "gt-bitmap.h"