/* Functions to support general ended bitmaps.
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005
- Free Software Foundation, Inc.
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003, 2004, 2005,
+ 2006, 2007 Free Software Foundation, Inc.
This file is part of GCC.
#include "obstack.h"
#include "ggc.h"
#include "bitmap.h"
+#include "hashtab.h"
+
+#ifdef GATHER_STATISTICS
+
+/* Store information about each particular bitmap. */
+struct bitmap_descriptor
+{
+ const char *function;
+ const char *file;
+ int line;
+ int allocated;
+ int created;
+ int peak;
+ int current;
+ int nsearches;
+};
+
+/* Hashtable mapping bitmap names to descriptors. */
+static htab_t bitmap_desc_hash;
+
+/* Hashtable helpers. */
+static hashval_t
+hash_descriptor (const void *p)
+{
+ const struct bitmap_descriptor *d = p;
+ return htab_hash_pointer (d->file) + d->line;
+}
+struct loc
+{
+ const char *file;
+ const char *function;
+ int line;
+};
+static int
+eq_descriptor (const void *p1, const void *p2)
+{
+ const struct bitmap_descriptor *d = p1;
+ const struct loc *l = p2;
+ return d->file == l->file && d->function == l->function && d->line == l->line;
+}
+
+/* For given file and line, return descriptor, create new if needed. */
+static struct bitmap_descriptor *
+bitmap_descriptor (const char *file, const char *function, int line)
+{
+ struct bitmap_descriptor **slot;
+ struct loc loc;
+
+ loc.file = file;
+ loc.function = function;
+ loc.line = line;
+
+ if (!bitmap_desc_hash)
+ bitmap_desc_hash = htab_create (10, hash_descriptor, eq_descriptor, NULL);
+
+ slot = (struct bitmap_descriptor **)
+ htab_find_slot_with_hash (bitmap_desc_hash, &loc,
+ htab_hash_pointer (file) + line,
+ 1);
+ if (*slot)
+ return *slot;
+ *slot = xcalloc (sizeof (**slot), 1);
+ (*slot)->file = file;
+ (*slot)->function = function;
+ (*slot)->line = line;
+ return *slot;
+}
+
+/* Register new bitmap. */
+void
+bitmap_register (bitmap b MEM_STAT_DECL)
+{
+ b->desc = bitmap_descriptor (_loc_name, _loc_function, _loc_line);
+ b->desc->created++;
+}
+
+/* Account the overhead. */
+static void
+register_overhead (bitmap b, int amount)
+{
+ b->desc->current += amount;
+ if (amount > 0)
+ b->desc->allocated += amount;
+ gcc_assert (b->desc->current >= 0);
+ if (b->desc->peak < b->desc->current)
+ b->desc->peak = b->desc->current;
+}
+#endif
/* Global data */
bitmap_element bitmap_zero_bits; /* An element of all zero bits. */
bitmap_elem_to_freelist (bitmap head, bitmap_element *elt)
{
bitmap_obstack *bit_obstack = head->obstack;
-
+
elt->next = NULL;
if (bit_obstack)
{
head->current = next != 0 ? next : prev;
if (head->current)
head->indx = head->current->indx;
- else
+ else
head->indx = 0;
}
+#ifdef GATHER_STATISTICS
+ register_overhead (head, -((int)sizeof (bitmap_element)));
+#endif
bitmap_elem_to_freelist (head, elt);
}
\f
{
bitmap_element *element;
bitmap_obstack *bit_obstack = head->obstack;
-
+
if (bit_obstack)
{
element = bit_obstack->elements;
-
+
if (element)
/* Use up the inner list first before looking at the next
element of the outer list. */
element = GGC_NEW (bitmap_element);
}
+#ifdef GATHER_STATISTICS
+ register_overhead (head, sizeof (bitmap_element));
+#endif
memset (element->bits, 0, sizeof (element->bits));
return element;
{
bitmap_element *prev;
bitmap_obstack *bit_obstack = head->obstack;
+#ifdef GATHER_STATISTICS
+ int n;
+#endif
if (!elt) return;
+#ifdef GATHER_STATISTICS
+ n = 0;
+ for (prev = elt; prev; prev = prev->next)
+ n++;
+ register_overhead (head, -sizeof (bitmap_element) * n);
+#endif
prev = elt->prev;
if (prev)
head->current = prev;
head->indx = prev->indx;
}
- }
+ }
else
{
head->first = NULL;
head->indx = 0;
}
- /* Put the entire list onto the free list in one operation. */
+ /* Put the entire list onto the free list in one operation. */
if (bit_obstack)
{
- elt->prev = bit_obstack->elements;
+ elt->prev = bit_obstack->elements;
bit_obstack->elements = elt;
}
else
{
if (!bit_obstack)
bit_obstack = &bitmap_default_obstack;
-
+
bit_obstack->elements = NULL;
bit_obstack->heads = NULL;
obstack_free (&bit_obstack->obstack, NULL);
it on the default bitmap obstack. */
bitmap
-bitmap_obstack_alloc (bitmap_obstack *bit_obstack)
+bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL)
{
bitmap map;
bit_obstack->heads = (void *)map->first;
else
map = XOBNEW (&bit_obstack->obstack, bitmap_head);
- bitmap_initialize (map, bit_obstack);
+ bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT);
+#ifdef GATHER_STATISTICS
+ register_overhead (map, sizeof (bitmap_head));
+#endif
return map;
}
/* Create a new GCd bitmap. */
bitmap
-bitmap_gc_alloc (void)
+bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL)
{
bitmap map;
map = GGC_NEW (struct bitmap_head_def);
- bitmap_initialize (map, NULL);
+ bitmap_initialize_stat (map, NULL PASS_MEM_STAT);
+#ifdef GATHER_STATISTICS
+ register_overhead (map, sizeof (bitmap_head));
+#endif
return map;
}
{
bitmap_clear (map);
map->first = (void *)map->obstack->heads;
+#ifdef GATHER_STATISTICS
+ register_overhead (map, -((int)sizeof (bitmap_head)));
+#endif
map->obstack->heads = map;
}
}
bitmap_element *element;
unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
+#ifdef GATHER_STATISTICS
+ head->desc->nsearches++;
+#endif
if (head->current == 0
|| head->indx == indx)
return head->current;
\f
#if GCC_VERSION < 3400
/* Table of number of set bits in a character, indexed by value of char. */
-static unsigned char popcount_table[] =
+static unsigned char popcount_table[] =
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
of BITMAP_WORD is not material. */
count += __builtin_popcountl (elt->bits[ix]);
#else
- count += bitmap_popcount (elt->bits[ix]);
+ count += bitmap_popcount (elt->bits[ix]);
#endif
}
}
return count;
}
-
+
/* Return the bit number of the first set bit in the bitmap. The
unsigned bit_no;
BITMAP_WORD word;
unsigned ix;
-
+
gcc_assert (elt);
bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS;
for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
word >>= 2, bit_no += 2;
if (!(word & 0x1))
word >>= 1, bit_no += 1;
-
+
gcc_assert (word & 1);
#endif
return bit_no;
if (!dst_elt)
dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
- else
+ else
dst_elt->indx = a_elt->indx;
for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
b_elt = b_elt->next;
}
}
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
gcc_assert (!dst->current == !dst->first);
if (dst->current)
bitmap_element *b_elt = b->first;
bitmap_element *next;
- if (a == b)
+ if (a == b)
return;
while (a_elt && b_elt)
gcc_assert (!a->current || a->indx == a->current->indx);
}
+
+/* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT
+ if non-NULL. CHANGED is true if the destination bitmap had already been
+ changed; the new value of CHANGED is returned. */
+
+static inline bool
+bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
+ bitmap_element *src_elt, bool changed)
+{
+ if (!changed && dst_elt && dst_elt->indx == src_elt->indx)
+ {
+ unsigned ix;
+
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ if (src_elt->bits[ix] != dst_elt->bits[ix])
+ {
+ dst_elt->bits[ix] = src_elt->bits[ix];
+ changed = true;
+ }
+ }
+ else
+ {
+ changed = true;
+ if (!dst_elt)
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx);
+ else
+ dst_elt->indx = src_elt->indx;
+ memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits));
+ }
+ return changed;
+}
+
+
+
/* DST = A & ~B */
-void
+bool
bitmap_and_compl (bitmap dst, bitmap a, bitmap b)
{
bitmap_element *dst_elt = dst->first;
bitmap_element *a_elt = a->first;
bitmap_element *b_elt = b->first;
bitmap_element *dst_prev = NULL;
+ bitmap_element **dst_prev_pnext = &dst->first;
+ bool changed = false;
gcc_assert (dst != a && dst != b);
-
+
if (a == b)
{
+ changed = !bitmap_empty_p (dst);
bitmap_clear (dst);
- return;
+ return changed;
}
while (a_elt)
{
- if (!b_elt || a_elt->indx < b_elt->indx)
+ while (b_elt && b_elt->indx < a_elt->indx)
+ b_elt = b_elt->next;
+
+ if (!b_elt || b_elt->indx > a_elt->indx)
{
- /* Copy a_elt. */
- if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
- else
- dst_elt->indx = a_elt->indx;
- memcpy (dst_elt->bits, a_elt->bits, sizeof (dst_elt->bits));
- dst_prev = dst_elt;
- dst_elt = dst_elt->next;
+ changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed);
+ dst_prev = *dst_prev_pnext;
+ dst_prev_pnext = &dst_prev->next;
+ dst_elt = *dst_prev_pnext;
a_elt = a_elt->next;
}
- else if (b_elt->indx < a_elt->indx)
- b_elt = b_elt->next;
+
else
{
/* Matching elts, generate A & ~B. */
unsigned ix;
BITMAP_WORD ior = 0;
- if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
- else
- dst_elt->indx = a_elt->indx;
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
{
- BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
- dst_elt->bits[ix] = r;
- ior |= r;
+ if (dst_elt->bits[ix] != r)
+ {
+ changed = true;
+ dst_elt->bits[ix] = r;
+ }
+ ior |= r;
+ }
}
+ else
+ {
+ bool new_element;
+ if (!dst_elt || dst_elt->indx > a_elt->indx)
+ {
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ new_element = true;
+ }
+ else
+ {
+ dst_elt->indx = a_elt->indx;
+ new_element = false;
+ }
+
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+
+ dst_elt->bits[ix] = r;
+ ior |= r;
+ }
+
+ if (ior)
+ changed = true;
+ else
+ {
+ changed |= !new_element;
+ bitmap_element_free (dst, dst_elt);
+ dst_elt = *dst_prev_pnext;
+ }
+ }
+
if (ior)
{
- dst_prev = dst_elt;
- dst_elt = dst_elt->next;
+ dst_prev = *dst_prev_pnext;
+ dst_prev_pnext = &dst_prev->next;
+ dst_elt = *dst_prev_pnext;
}
a_elt = a_elt->next;
b_elt = b_elt->next;
}
}
- bitmap_elt_clear_from (dst, dst_elt);
+
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
+
+ if (dst_elt)
+ {
+ changed = true;
+ bitmap_elt_clear_from (dst, dst_elt);
+ }
gcc_assert (!dst->current == !dst->first);
if (dst->current)
dst->indx = dst->current->indx;
+
+ return changed;
}
/* A &= ~B. Returns true if A changes */
return changed != 0;
}
+/* Set COUNT bits from START in HEAD. */
+void
+bitmap_set_range (bitmap head, unsigned int start, unsigned int count)
+{
+ unsigned int first_index, end_bit_plus1, last_index;
+ bitmap_element *elt, *elt_prev;
+ unsigned int i;
+
+ if (!count)
+ return;
+
+ first_index = start / BITMAP_ELEMENT_ALL_BITS;
+ end_bit_plus1 = start + count;
+ last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
+ elt = bitmap_find_bit (head, start);
+
+ /* If bitmap_find_bit returns zero, the current is the closest block
+ to the result. Otherwise, just use bitmap_element_allocate to
+ ensure ELT is set; in the loop below, ELT == NULL means "insert
+ at the end of the bitmap". */
+ if (!elt)
+ {
+ elt = bitmap_element_allocate (head);
+ elt->indx = first_index;
+ bitmap_element_link (head, elt);
+ }
+
+ gcc_assert (elt->indx == first_index);
+ elt_prev = elt->prev;
+ for (i = first_index; i <= last_index; i++)
+ {
+ unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS;
+ unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS;
+
+ unsigned int first_word_to_mod;
+ BITMAP_WORD first_mask;
+ unsigned int last_word_to_mod;
+ BITMAP_WORD last_mask;
+ unsigned int ix;
+
+ if (!elt || elt->indx != i)
+ elt = bitmap_elt_insert_after (head, elt_prev, i);
+
+ if (elt_start_bit <= start)
+ {
+ /* The first bit to turn on is somewhere inside this
+ elt. */
+ first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
+
+ /* This mask should have 1s in all bits >= start position. */
+ first_mask =
+ (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
+ first_mask = ~first_mask;
+ }
+ else
+ {
+ /* The first bit to turn on is below this start of this elt. */
+ first_word_to_mod = 0;
+ first_mask = ~(BITMAP_WORD) 0;
+ }
+
+ if (elt_end_bit_plus1 <= end_bit_plus1)
+ {
+ /* The last bit to turn on is beyond this elt. */
+ last_word_to_mod = BITMAP_ELEMENT_WORDS - 1;
+ last_mask = ~(BITMAP_WORD) 0;
+ }
+ else
+ {
+ /* The last bit to turn on is inside to this elt. */
+ last_word_to_mod =
+ (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
+
+ /* The last mask should have 1s below the end bit. */
+ last_mask =
+ (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1;
+ }
+
+ if (first_word_to_mod == last_word_to_mod)
+ {
+ BITMAP_WORD mask = first_mask & last_mask;
+ elt->bits[first_word_to_mod] |= mask;
+ }
+ else
+ {
+ elt->bits[first_word_to_mod] |= first_mask;
+ if (BITMAP_ELEMENT_WORDS > 2)
+ for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++)
+ elt->bits[ix] = ~(BITMAP_WORD) 0;
+ elt->bits[last_word_to_mod] |= last_mask;
+ }
+
+ elt_prev = elt;
+ elt = elt->next;
+ }
+
+ head->current = elt ? elt : elt_prev;
+ head->indx = head->current->indx;
+}
+
/* Clear COUNT bits from START in HEAD. */
void
bitmap_clear_range (bitmap head, unsigned int start, unsigned int count)
{
- unsigned int first_index = start / BITMAP_ELEMENT_ALL_BITS;
- unsigned int end_bit_plus1 = start + count;
- unsigned int end_bit = end_bit_plus1 - 1;
- unsigned int last_index = (end_bit) / BITMAP_ELEMENT_ALL_BITS;
- bitmap_element *elt = bitmap_find_bit (head, start);
+ unsigned int first_index, end_bit_plus1, last_index;
+ bitmap_element *elt;
+
+ if (!count)
+ return;
+
+ first_index = start / BITMAP_ELEMENT_ALL_BITS;
+ end_bit_plus1 = start + count;
+ last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS;
+ elt = bitmap_find_bit (head, start);
/* If bitmap_find_bit returns zero, the current is the closest block
to the result. If the current is less than first index, find the
next one. Otherwise, just set elt to be current. */
if (!elt)
- {
+ {
if (head->current)
{
if (head->indx < first_index)
if (!elt)
return;
}
- else
+ else
elt = head->current;
}
else
if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1)
/* Get rid of the entire elt and go to the next one. */
bitmap_element_free (head, elt);
- else
+ else
{
/* Going to have to knock out some bits in this elt. */
- unsigned int first_word_to_mod;
- BITMAP_WORD first_mask;
+ unsigned int first_word_to_mod;
+ BITMAP_WORD first_mask;
unsigned int last_word_to_mod;
BITMAP_WORD last_mask;
unsigned int i;
first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS;
/* This mask should have 1s in all bits >= start position. */
- first_mask =
+ first_mask =
(((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1;
first_mask = ~first_mask;
}
first_word_to_mod = 0;
first_mask = 0;
first_mask = ~first_mask;
- }
-
+ }
+
if (elt_end_bit_plus1 <= end_bit_plus1)
{
/* The last bit to turn off is beyond this elt. */
else
{
/* The last bit to turn off is inside to this elt. */
- last_word_to_mod =
+ last_word_to_mod =
(end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS;
/* The last mask should have 1s below the end bit. */
- last_mask =
+ last_mask =
(((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1;
}
else
{
elt->bits[first_word_to_mod] &= ~first_mask;
- for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
- elt->bits[i] = 0;
+ if (BITMAP_ELEMENT_WORDS > 2)
+ for (i = first_word_to_mod + 1; i < last_word_to_mod; i++)
+ elt->bits[i] = 0;
elt->bits[last_word_to_mod] &= ~last_mask;
}
for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
}
elt = next_elt;
}
-
+
if (elt)
{
head->current = elt;
return;
}
+
+/* Insert an element corresponding to A_ELT | B_ELT after DST_PREV,
+ overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap
+ had already been changed; the new value of CHANGED is returned. */
+
+static inline bool
+bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev,
+ bitmap_element *a_elt, bitmap_element *b_elt,
+ bool changed)
+{
+ gcc_assert (a_elt || b_elt);
+
+ if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+ {
+ /* Matching elts, generate A | B. */
+ unsigned ix;
+
+ if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
+ {
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
+ if (r != dst_elt->bits[ix])
+ {
+ dst_elt->bits[ix] = r;
+ changed = true;
+ }
+ }
+ }
+ else
+ {
+ changed = true;
+ if (!dst_elt)
+ dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
+ else
+ dst_elt->indx = a_elt->indx;
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
+ dst_elt->bits[ix] = r;
+ }
+ }
+ }
+ else
+ {
+ /* Copy a single element. */
+ bitmap_element *src;
+
+ if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
+ src = a_elt;
+ else
+ src = b_elt;
+
+ gcc_assert (src);
+ changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed);
+ }
+ return changed;
+}
+
+
/* DST = A | B. Return true if DST changes. */
bool
bitmap_element *a_elt = a->first;
bitmap_element *b_elt = b->first;
bitmap_element *dst_prev = NULL;
- bool changed = false;
+ bitmap_element **dst_prev_pnext = &dst->first;
+ bool changed = false;
gcc_assert (dst != a && dst != b);
while (a_elt || b_elt)
{
+ changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed);
+
if (a_elt && b_elt && a_elt->indx == b_elt->indx)
{
- /* Matching elts, generate A | B. */
- unsigned ix;
-
- if (!changed && dst_elt && dst_elt->indx == a_elt->indx)
- {
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
- {
- BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-
- if (r != dst_elt->bits[ix])
- {
- dst_elt->bits[ix] = r;
- changed = true;
- }
- }
- }
- else
- {
- changed = true;
- if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx);
- else
- dst_elt->indx = a_elt->indx;
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
- {
- BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-
- dst_elt->bits[ix] = r;
- }
- }
a_elt = a_elt->next;
b_elt = b_elt->next;
- dst_prev = dst_elt;
- dst_elt = dst_elt->next;
}
else
{
- /* Copy a single element. */
- bitmap_element *src;
-
- if (!b_elt || (a_elt && a_elt->indx < b_elt->indx))
- {
- src = a_elt;
- a_elt = a_elt->next;
- }
- else
- {
- src = b_elt;
- b_elt = b_elt->next;
- }
-
- if (!changed && dst_elt && dst_elt->indx == src->indx)
- {
- unsigned ix;
-
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
- if (src->bits[ix] != dst_elt->bits[ix])
- {
- dst_elt->bits[ix] = src->bits[ix];
- changed = true;
- }
- }
- else
- {
- changed = true;
- if (!dst_elt)
- dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
- else
- dst_elt->indx = src->indx;
- memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
- }
-
- dst_prev = dst_elt;
- dst_elt = dst_elt->next;
+ if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+ a_elt = a_elt->next;
+ else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
+ b_elt = b_elt->next;
}
+
+ dst_prev = *dst_prev_pnext;
+ dst_prev_pnext = &dst_prev->next;
+ dst_elt = *dst_prev_pnext;
}
if (dst_elt)
bitmap_element *a_elt = a->first;
bitmap_element *b_elt = b->first;
bitmap_element *a_prev = NULL;
+ bitmap_element **a_prev_pnext = &a->first;
bool changed = false;
if (a == b)
while (b_elt)
{
- if (!a_elt || b_elt->indx < a_elt->indx)
+ /* If A lags behind B, just advance it. */
+ if (!a_elt || a_elt->indx == b_elt->indx)
{
- /* Copy b_elt. */
- bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx);
- memcpy (dst->bits, b_elt->bits, sizeof (dst->bits));
- a_prev = dst;
+ changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
b_elt = b_elt->next;
- changed = true;
- }
- else if (a_elt->indx < b_elt->indx)
- {
- a_prev = a_elt;
- a_elt = a_elt->next;
}
- else
+ else if (a_elt->indx > b_elt->indx)
{
- /* Matching elts, generate A |= B. */
- unsigned ix;
-
- if (changed)
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
- {
- BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-
- a_elt->bits[ix] = r;
- }
- else
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
- {
- BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix];
-
- if (a_elt->bits[ix] != r)
- {
- changed = true;
- a_elt->bits[ix] = r;
- }
- }
+ changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed);
b_elt = b_elt->next;
- a_prev = a_elt;
- a_elt = a_elt->next;
}
+
+ a_prev = *a_prev_pnext;
+ a_prev_pnext = &a_prev->next;
+ a_elt = *a_prev_pnext;
}
+
gcc_assert (!a->current == !a->first);
if (a->current)
a->indx = a->current->indx;
if (!dst_elt)
dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx);
- else
+ else
dst_elt->indx = src->indx;
memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits));
dst_prev = dst_elt;
dst_elt = dst_elt->next;
}
}
+ /* Ensure that dst->current is valid. */
+ dst->current = dst->first;
bitmap_elt_clear_from (dst, dst_elt);
gcc_assert (!dst->current == !dst->first);
if (dst->current)
bitmap_element *a_elt;
bitmap_element *b_elt;
unsigned ix;
-
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;
a_elt = a_elt->next, b_elt = b_elt->next)
bitmap_element *a_elt;
bitmap_element *b_elt;
unsigned ix;
-
+
for (a_elt = a->first, b_elt = b->first;
a_elt && b_elt;)
{
/* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */
bool
-bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap from1, bitmap from2)
+bitmap_ior_and_compl (bitmap dst, bitmap a, bitmap b, bitmap kill)
{
- bitmap_head tmp;
- bool changed;
+ bool changed = false;
- bitmap_initialize (&tmp, &bitmap_default_obstack);
- bitmap_and_compl (&tmp, from1, from2);
- changed = bitmap_ior (dst, a, &tmp);
- bitmap_clear (&tmp);
+ bitmap_element *dst_elt = dst->first;
+ bitmap_element *a_elt = a->first;
+ bitmap_element *b_elt = b->first;
+ bitmap_element *kill_elt = kill->first;
+ bitmap_element *dst_prev = NULL;
+ bitmap_element **dst_prev_pnext = &dst->first;
+
+ gcc_assert (dst != a && dst != b && dst != kill);
+
+ /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */
+ if (b == kill || bitmap_empty_p (b))
+ {
+ changed = !bitmap_equal_p (dst, a);
+ if (changed)
+ bitmap_copy (dst, a);
+ return changed;
+ }
+ if (bitmap_empty_p (kill))
+ return bitmap_ior (dst, a, b);
+ if (bitmap_empty_p (a))
+ return bitmap_and_compl (dst, b, kill);
+
+ while (a_elt || b_elt)
+ {
+ bool new_element = false;
+
+ if (b_elt)
+ while (kill_elt && kill_elt->indx < b_elt->indx)
+ kill_elt = kill_elt->next;
+
+ if (b_elt && kill_elt && kill_elt->indx == b_elt->indx
+ && (!a_elt || a_elt->indx >= b_elt->indx))
+ {
+ bitmap_element tmp_elt;
+ unsigned ix;
+
+ BITMAP_WORD ior = 0;
+ tmp_elt.indx = b_elt->indx;
+ for (ix = BITMAP_ELEMENT_WORDS; ix--;)
+ {
+ BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix];
+ ior |= r;
+ tmp_elt.bits[ix] = r;
+ }
+
+ if (ior)
+ {
+ changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
+ a_elt, &tmp_elt, changed);
+ new_element = true;
+ if (a_elt && a_elt->indx == b_elt->indx)
+ a_elt = a_elt->next;
+ }
+
+ b_elt = b_elt->next;
+ kill_elt = kill_elt->next;
+ }
+ else
+ {
+ changed = bitmap_elt_ior (dst, dst_elt, dst_prev,
+ a_elt, b_elt, changed);
+ new_element = true;
+
+ if (a_elt && b_elt && a_elt->indx == b_elt->indx)
+ {
+ a_elt = a_elt->next;
+ b_elt = b_elt->next;
+ }
+ else
+ {
+ if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx))
+ a_elt = a_elt->next;
+ else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx))
+ b_elt = b_elt->next;
+ }
+ }
+
+ if (new_element)
+ {
+ dst_prev = *dst_prev_pnext;
+ dst_prev_pnext = &dst_prev->next;
+ dst_elt = *dst_prev_pnext;
+ }
+ }
+
+ if (dst_elt)
+ {
+ changed = true;
+ bitmap_elt_clear_from (dst, dst_elt);
+ }
+ gcc_assert (!dst->current == !dst->first);
+ if (dst->current)
+ dst->indx = dst->current->indx;
return changed;
}
{
bitmap_head tmp;
bool changed;
-
+
bitmap_initialize (&tmp, &bitmap_default_obstack);
bitmap_and_compl (&tmp, from1, from2);
changed = bitmap_ior_into (a, &tmp);
return changed;
}
+
\f
/* Debugging function to print out the contents of a bitmap. */
}
fputs (suffix, file);
}
+#ifdef GATHER_STATISTICS
+
+
+/* Used to accumulate statistics about bitmap sizes. */
+struct output_info
+{
+ int count;
+ int size;
+};
+
+/* Called via htab_traverse. Output bitmap descriptor pointed out by SLOT
+ and update statistics. */
+static int
+print_statistics (void **slot, void *b)
+{
+ struct bitmap_descriptor *d = (struct bitmap_descriptor *) *slot;
+ struct output_info *i = (struct output_info *) b;
+ char s[4096];
+
+ if (d->allocated)
+ {
+ const char *s1 = d->file;
+ const char *s2;
+ while ((s2 = strstr (s1, "gcc/")))
+ s1 = s2 + 4;
+ sprintf (s, "%s:%i (%s)", s1, d->line, d->function);
+ s[41] = 0;
+ fprintf (stderr, "%-41s %6d %10d %10d %10d %10d\n", s,
+ d->created, d->allocated, d->peak, d->current, d->nsearches);
+ i->size += d->allocated;
+ i->count += d->created;
+ }
+ return 1;
+}
+#endif
+/* Output per-bitmap memory usage statistics. */
+void
+dump_bitmap_statistics (void)
+{
+#ifdef GATHER_STATISTICS
+ struct output_info info;
+
+ if (!bitmap_desc_hash)
+ return;
+
+ fprintf (stderr, "\nBitmap Overall "
+ "Allocated Peak Leak searched "
+ " per search\n");
+ fprintf (stderr, "---------------------------------------------------------------------------------\n");
+ info.count = 0;
+ info.size = 0;
+ htab_traverse (bitmap_desc_hash, print_statistics, &info);
+ fprintf (stderr, "---------------------------------------------------------------------------------\n");
+ fprintf (stderr, "%-40s %7d %10d\n",
+ "Total", info.count, info.size);
+ fprintf (stderr, "---------------------------------------------------------------------------------\n");
+#endif
+}
+
+/* Compute hash of bitmap (for purposes of hashing). */
+hashval_t
+bitmap_hash (bitmap head)
+{
+ bitmap_element *ptr;
+ BITMAP_WORD hash = 0;
+ int ix;
+
+ for (ptr = head->first; ptr; ptr = ptr->next)
+ {
+ hash ^= ptr->indx;
+ for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++)
+ hash ^= ptr->bits[ix];
+ }
+ return (hashval_t)hash;
+}
#include "gt-bitmap.h"
OSDN Git Service
