aboutsummaryrefslogtreecommitdiff
path: root/gcc
diff options
context:
space:
mode:
authorKenneth Zadeck <zadeck@naturalbridge.com>2005-05-12 03:01:44 +0000
committerDaniel Berlin <dberlin@gcc.gnu.org>2005-05-12 03:01:44 +0000
commit5765e552580a9b01c690fcb63dd6b86899232919 (patch)
tree131aaf5b4cd54ed92924c1eec55336a2d17fde92 /gcc
parentcca1655eabb86897dc2dfd5aa2830d07a1cc83ca (diff)
downloadgcc-5765e552580a9b01c690fcb63dd6b86899232919.zip
gcc-5765e552580a9b01c690fcb63dd6b86899232919.tar.gz
gcc-5765e552580a9b01c690fcb63dd6b86899232919.tar.bz2
bitmap.c (bitmap_elmt_to_freelist, [...]): Changed freelist structure.
2005-05-11 Kenneth Zadeck <zadeck@naturalbridge.com> * bitmap.c (bitmap_elmt_to_freelist, bitmap_element_allocate, bitmap_elt_clear_from, bitmap_clear): Changed freelist structure. * bitmap.h: Fixed comments. From-SVN: r99605
Diffstat (limited to 'gcc')
-rw-r--r--gcc/ChangeLog6
-rw-r--r--gcc/bitmap.c73
-rw-r--r--gcc/bitmap.h13
3 files changed, 71 insertions, 21 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f92014e..b3f576d 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2005-05-11 Kenneth Zadeck <zadeck@naturalbridge.com>
+
+ * bitmap.c (bitmap_elmt_to_freelist, bitmap_element_allocate,
+ bitmap_elt_clear_from, bitmap_clear): Changed freelist structure.
+ * bitmap.h: Fixed comments.
+
2005-05-11 Richard Henderson <rth@redhat.com>
PR target/21412
diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 2cf4c8c..dd56bba 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -51,14 +51,15 @@ bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
{
bitmap_obstack *bit_obstack = head->obstack;
+ elt->next = NULL;
if (bit_obstack)
{
- elt->next = bit_obstack->elements;
+ elt->prev = bit_obstack->elements;
bit_obstack->elements = elt;
}
else
{
- elt->next = bitmap_ggc_free;
+ elt->prev = bitmap_ggc_free;
bitmap_ggc_free = elt;
}
}
@@ -105,7 +106,16 @@ bitmap_element_allocate (bitmap head)
element = bit_obstack->elements;
if (element)
- bit_obstack->elements = element->next;
+ /* Use up the inner list first before looking at the next
+ element of the outer list. */
+ if (element->next)
+ {
+ bit_obstack->elements = element->next;
+ bit_obstack->elements->prev = element->prev;
+ }
+ else
+ /* Inner list was just a singleton. */
+ bit_obstack->elements = element->prev;
else
element = XOBNEW (&bit_obstack->obstack, bitmap_element);
}
@@ -113,7 +123,16 @@ bitmap_element_allocate (bitmap head)
{
element = bitmap_ggc_free;
if (element)
- bitmap_ggc_free = element->next;
+ /* Use up the inner list first before looking at the next
+ element of the outer list. */
+ if (element->next)
+ {
+ bitmap_ggc_free = element->next;
+ bitmap_ggc_free->prev = element->prev;
+ }
+ else
+ /* Inner list was just a singleton. */
+ bitmap_ggc_free = element->prev;
else
element = GGC_NEW (bitmap_element);
}
@@ -128,13 +147,38 @@ bitmap_element_allocate (bitmap head)
void
bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
{
- bitmap_element *next;
+ bitmap_element *prev;
+ bitmap_obstack *bit_obstack = head->obstack;
+
+ if (!elt) return;
- while (elt)
+ prev = elt->prev;
+ if (prev)
{
- next = elt->next;
- bitmap_element_free (head, elt);
- elt = next;
+ prev->next = NULL;
+ if (head->current->indx > prev->indx)
+ {
+ head->current = prev;
+ head->indx = prev->indx;
+ }
+ }
+ else
+ {
+ head->first = NULL;
+ head->current = NULL;
+ head->indx = 0;
+ }
+
+ /* Put the entire list onto the free list in one operation. */
+ if (bit_obstack)
+ {
+ elt->prev = bit_obstack->elements;
+ bit_obstack->elements = elt;
+ }
+ else
+ {
+ elt->prev = bitmap_ggc_free;
+ bitmap_ggc_free = elt;
}
}
@@ -143,15 +187,8 @@ bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
inline void
bitmap_clear (bitmap head)
{
- bitmap_element *element, *next;
-
- for (element = head->first; element != 0; element = next)
- {
- next = element->next;
- bitmap_elem_to_freelist (head, element);
- }
-
- head->first = head->current = 0;
+ if (head->first)
+ bitmap_elt_clear_from (head, head->first);
}
/* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize
diff --git a/gcc/bitmap.h b/gcc/bitmap.h
index 2915623..3c3b3c1 100644
--- a/gcc/bitmap.h
+++ b/gcc/bitmap.h
@@ -49,8 +49,15 @@ typedef struct bitmap_obstack GTY (())
/* Bitmap set element. We use a linked list to hold only the bits that
are set. This allows for use to grow the bitset dynamically without
- having to realloc and copy a giant bit array. The `prev' field is
- undefined for an element on the free list. */
+ having to realloc and copy a giant bit array.
+
+ The free list is implemented as a list of lists. There is one
+ outer list connected together by prev fields. Each element of that
+ outer is an inner list (that may consist only of the outer list
+ element) that are connected by the next fields. The prev pointer
+ is undefined for interior elements. This allows
+ bitmap_elt_clear_from to be implemented in unit time rather than
+ linear in the number of elements to be freed. */
typedef struct bitmap_element_def GTY(())
{
@@ -129,7 +136,7 @@ extern void debug_bitmap_file (FILE *, bitmap);
/* Print a bitmap. */
extern void bitmap_print (FILE *, bitmap, const char *, const char *);
-/* Initialize and releas a bitmap obstack. */
+/* Initialize and release a bitmap obstack. */
extern void bitmap_obstack_initialize (bitmap_obstack *);
extern void bitmap_obstack_release (bitmap_obstack *);