/* 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.
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);
+ 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 (dst_elt->bits[ix] != r)
+ {
+ changed = true;
+ dst_elt->bits[ix] = r;
+ }
+ ior |= r;
+ }
+ }
else
- dst_elt->indx = a_elt->indx;
- for (ix = BITMAP_ELEMENT_WORDS; ix--;)
{
- BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix];
+ 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;
+ }
- dst_elt->bits[ix] = r;
- ior |= r;
+ 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;
}
}
+
/* Ensure that dst->current is valid. */
dst->current = dst->first;
- bitmap_elt_clear_from (dst, dst_elt);
+
+ 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
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++)
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;
+ 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;
/* 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;
}
return changed;
}
+
\f
/* Debugging function to print out the contents of a bitmap. */
OSDN Git Service
